목록1103 (1)

프로그래밍에 대한 고찰 및 생각

[알고리즘][5][백준_1103][Python3] - 게임

문제이해 n x m 의 보드에 숫자들이 주어지고 특정지점에서 출발해서 특정조건에 따라 상하좌우로 이동하며 최대,최소의 경우를 구하는 전형적인 문제이다. 다만 여기서는 무한번 움직인다면 -1을 출력해야하므로 이부분이 까다로울수 있다. 알고리즘 전략 [0][0] 지점에서 시작해서 해당칸의 숫자만큼 상하좌우로 이동할수 있으므로 모든 경우를 확인해봐야한다. 따라서 재귀함수를 이용한 brute-force 와 메모이제이션을 이용해 DP로 해결하면 될것같다. 문제에따르면 최대한 보드 내에서 많이 움직여야하는데 보드바깥으로 나가거나 H를 만나면 종료되므로 해당조건으로 설계하면 이부분은 간단하다. 중요한 부분은 무한번 움직이는것을 어떻게 캐치해낼것인지이다. 쉽게생각하면 이런경우를 떠올릴수 있다. 위 상황은 1-3을 보면..
알고리즘/백준 2020. 2. 2. 15:35
이전 Prev 1 Next 다음