3 3
111
111
111
일 때 5가 아니라 9를 출력하네요.
dfs로 푸실 계획이라면 모든 경로를 다 방문할 수 있어야 하는데,
위처럼 푸실 경우 map[x][y] = '0'에 의해 한 경로로만 쭉 가서 9를 출력하게 됩니다
2178번 - 미로 탐색
3 3
111
111
111
일 때 5가 아니라 9를 출력하네요.
dfs로 푸실 계획이라면 모든 경로를 다 방문할 수 있어야 하는데,
위처럼 푸실 경우 map[x][y] = '0'에 의해 한 경로로만 쭉 가서 9를 출력하게 됩니다
네 dfs로 푸시려면 윗 분 말씀대로 고치시면 될 것 같네요.
그러면 아마 시간초과를 경험하게 되실 것 같습니다..ㅠ
dfs로 풀어보진 않아서 확답은 못 드리겠지만 가능하면 아래, 오른쪽으로 우선 움직이기, 입구에서 미로의 절반까지만 dfs로 방문하고, 출구에서 출발해서 나머지 절반까지 도달해서 dfs의 깊이 줄이기 등을 활용하면 시간 내에 될 지도 모르겠네요.
근데 제 생각에는 bfs로 이 문제를 푸시는 게 편할 것 같습니다. bfs로는 출구에 도착하는 순간 그게 최소거리임을 알 수도 있을 뿐더러 어떤 입력에도 비슷한 성능을 낼 것 같습니다. (dfs로 전부 다 개방된 미로를 풀게 되면 가지수가 꽤 많을 것 같네요)
저도 처음에 탐색 공부했을때 dfs밖에 할줄몰라서 비슷하게 당했던 경험이 있는데요...
indioindio 님이 말씀하신대로 재귀의깊이를 줄이면 가능성이 있긴한데
입력하는 테스트케이스를 확인하면 dfs로 하면 타임리밋이 나는 경우를 입력받거든요...
예를들면 전부다 갈수있는 길로 체크된 경우 였었나? 그런 경우에는 mXn의 수만큼 재귀가 깊어져버려서.. 헤어나오지 못한다는...
현재 위치를 pos++이 아니라 적절히 deque해서 푸시면 될 것 같습니다.
맞으셨다니 다행이네요. 고수는 절대 아닙니다..ㅋㅋ
그래도 재귀함수에 대해서 약간 팁을 드리자면 재귀함수를 자기 자신을 호출하는 함수라고 생각하시기보다는, 점화식이라고 생각하시는 게 편할 것 같습니다.
일례로 a 기둥에 있는 N개의 원판을 a,b,c 의 기둥에서 c로 옮기는 하노이의 탑 문제를 생각해보시면, (풀어보셨는지 모르겠지만 안 푸셨다면 한 번 풀어보세요)
f(n, src, dst, mid)라는 함수를
f(n-1, a, b, c)
move 1 from a to c
f(n-1, b, c, a)
로 해서 초기조건을 더해서 주로 풉니다.
이 코드를 f가 자기 자신을 호출한다고 생각해서 계속 인자를 적어나가면 밑도 끝도 없지만, 점화식이라고 생각하면 편해집니다.
f(n, src, dst, mid)를 어떻게 작동 하는지는 모르겠으나 n개의 원반을 src에서 dst로, mid를 이용해 아주 잘 옮겨주는 함수라고 해봅시다.
그럼 위 함수를 이용해서 n 개를 a에서 c로 움직이려면,
n-1개를 우선 a에서 b로 옮긴 다음 (f(n-1, a, b, c)를 하면 되겠죠? 어떻게 해서 잘 옮겨주는지는 모르겠지만)
맨 밑에 한 개를 a 에서 c로 옮긴 다음,
n-1개를 다시 b에서 c로 옮기면 됩니다. // f(n-1, b, c, a)
위의 예시처럼 어떤 함수가 부분문제를 잘 해결해준다고 가정하고 점화식을 작성하듯이 코딩을 해주면 쉽게 재귀함수에 접근하실 수 있을 것 같네요.
댓글을 작성하려면 로그인해야 합니다.
kcm5680 8년 전 1
예제 답은 맞게 나오는데 채점에서 틀리게 나오네요..
무엇이 문제일까요 고수님들 답변좀 부탁드립니다.