백준 1103번 게임

< 백준 1103번 게임 - 마포 코딩박 >

사용한 알고리즘:  DFS + DP


 Grid 의 칸마다 숫자가 주어지고, 상하좌우로 그 숫자만큼 이동한다. 이때 최대 이동 가능수를 구한다. 처음 시작하는 지점은 왼쪽위(0,0) 지점이다.
처음 시작도 1번으로 카운트 해줘야 한다.
처음 시작을 0번으로 하고, 대신 마지막에 Grid밖으로 움직이는 것을 +1번으로 카운트 해주었다.

문제풀이는 다음과 같다.
(1) (코드: 12~36)
 시작위치 (0,0) 에서 DFS를 사용해 상하좌우로 탐색해주었다.

(2) (코드: dp[50][50])
 dp[i][j] : (i,j) 위치에서 최대 이동가능 횟수 로 저장해주어, 반복적인 탐색을 피해줬다.

(3) (코드: visited[50][50])
 이미 방문했던 위치를 다시 방문할 경우, cycle이 생긴 경우이다. 즉 동전을 무한대로 움직일 수 있는경우이다. 이를 체크해주어 이경우 -1을 출력해주었다.