프로그래머스. 미로 탈출 명령어

https://school.programmers.co.kr/learn/courses/30/lessons/150365

프로그래머스

 

미로에서 탈출한 경로의 총길이는 무조건 k 여야 하고, 문자열로 나타냈을때 사전 순으로 가장 빠른 경로로 탈출해야한다.

 

방향 알파벳 l,r,u,d 를 사전순으로 나타내면 d,l,r,u 이다.

따라서 현재 좌표에서 이동하는 순서를 d(아래), l(왼쪽), r(오른쪽), u(위) 순서로 이동해보면 된다.

 

dfs 로 이동하다가 깊이가 k (총 k번 이동함) 일때 도착지점이면 해당 경로가 답이다.

우리는 애초에 이동을 d,l,r,u 순서대로 했기 때문에 최초로 얻게되는 경로가 무조건 사전순 빠른 경로가 된다. 

 

이 문제는 같은 곳을 다시 방문가능하기 때문에 그냥 한번 방문했던곳을 방문하지 않도록 처리하면 안되고, 몇번째 이동에 해당 좌표로 이동했는지를 따져줘야 한다.

 

visited[2501][51][51] // vistied[n][x][y] 는 n번째 이동에 x,y 좌표에 도달했다