이 문제는 모든 경우를 따져봐야 합니다. 즉 완전 탐색입니다. 완전 탐색을 위해서 bfs를 이용해야 합니다. dfs를 이용해서 탐색하게 되면 시간초과를 만나게 됩니다. 한쪽만 잘 못 파고 들어가게 되면 dfs 같은 경우 오래 걸릴 수 있기 때문입니다. 이 문제는 최단 거리를 구하라는 뜻과 같습니다. 최단 거리를 구하는 문제의 경우에 dfs보다는 bfs를 이용해서 푸는 것이 좋습니다.
bfs
bfs의 구현에서 주의할 점은 # queue에 좌표를 넣자마자 visited 배열을 체크해주는 것이 중요합니다. queue를 사욯하여 구현하였고 x,y좌표와 현재까지 이동한 거리를 저장할 수 있도록 Pos 클래스를 작성하였습니다.