문제 설명
(x, y)에서 출발해서 (r, c)로 이동할 때 미로에서 탈출한 경로를 반환하는 문제다. 이렇게 보면 단순한 탐색 문제인 듯 싶지만, 여기에는 세 가지 조건이 있다.
첫째. 격자 바깥으로는 나갈 수 없다. 이건 다른 탐색 문제에서도 거의 기본으로 나오는 조건이라 넘어가고.
둘째. (x, y)에서 (r, c)까지 이동하는 거리는 총 k여야 한다. 즉, 무조건 k번 움직여야 한다는 뜻이다. 이때 (x, y)나 (r, c) 격자를 포함해서 한 번 방문했던 격자도 다시 방문할 수 있다.
셋째. 미로에서 탈출한 경로는 무조건 사전 순으로 제일 빠른 것이 답이 된다.
문제 풀이
첫 번째 접근
처음에는 k만큼 경로를 만들어서 탐색하면 되지 않나 싶었다. 그러나 k의 길이가 1부터 2500까지라는 걸 보고 접었다. 최악의 경우 4의 2500 제곱이라는 의미인데... 음... 이러면 어렵지.
일단 깊이 우선 탐색인 건 알겠는데, 그 다음 단계로 넘어가지 못해서 결국 다른 사람의 풀이를 봤다.
두 번째 접근
깊이 우선 탐색이 맞긴 했다. 그리고 새로운 접근 방법을 봤는데 바로 남은 거리를 계산하는 거다.
먼저 주어진 k의 남은 거리가 0이고 현재 좌표와 목표 좌표 사이의 거리가 0이면 이는 답이므로 answer에 만든 s를 넣어주고 true를 반환한다.
그리고 위의 조건이 아니라면 총 4가지 방향으로 탐색한다. 이때 탐색은 사전 순으로 이뤄져야 한다. 이렇게 새로 만든 좌표가 격자 안에 존재한다면 새로 만든 좌표와 목표 좌표 사이의 거리를 구한다. 그리고 k와 현재 좌표와 목표 좌표 사이의 거리를 2로 나눠서 나머지가 같다면 새로 만든 좌표를 탐색한다. 이때 탐색한 위치의 문자를 s에 붙여준다. 그리고 해당 탐색이 참이라면 참을 반환한다.
풀이 링크
배운 점
재귀 함수에서 return
dfs 문제를 풀면서 재귀는 여러 번 써봤지만 여전히 return을 제대로 다루지 못했다. 충족 조건에 리턴을 쓰는 건 알았지만 해당 조건을 충족하고 무조건 종료해야 할 때 어떻게 반환을 해야 한다는 점을 몰랐다. 그러나 위의 풀이를 보면서 return을 어디에 써야 정확하게 재귀를 탈출하게 되는지 알게 됐다.
일단 충족 조건에 리턴을 쓴다. 그리고 재귀 함수를 호출 할 때 호출된 해당 함수가 참이라면 참을 반환하도록 한다. 이렇게 되면 충족 조건을 처음 만족한 값이 if 조건문에 걸리면서 참을 반환하면서 재귀함수가 종료된다. 만일 이렇게 참을 반환하지 못했다면 결국 맨 마지막에 있는 false를 반환하게 된다.
가지치기 조건
반환 문제 뿐만 아니라 주어진 k를 어떻게 하면 다 쓸 수 있을지 또한 의문이었다. 이 부분은 해당 풀이처럼 현재 좌표와 목표 좌표의 거리를 계산하여 비교해주면 된다는 것을 배웠다.
//두 좌표 사이의 거리 계산
Math.abs(nextY - endY) + Math.abs(nextX - endX);또한 풀이에서 언급한 가지치기 조건을 넣어주지 않으면 시간 초과가 난다. k가 2,500까지 가능하니...
