10^6 만큼만 재귀호출이 되지 않습니다.
dfs 탐색 시, 가중치가 큰 것부터 먼저 탐색했다면 나중에 가중치가 작은 것으로 다시 탐색해주어야하므로 exponential할 것으로 생각됩니다.
다익스트라를 돌리듯이 현재까지 방문한 grid의 집합(4방향으로 다 이웃한 하나의 집합이겠죠?) 중 새로 추가되는 집합의 원소로서 그 가중치가 가장 작은 걸 계속 넣어준다면 O(n^2 log n)에 풀 수 있습니다.
등장하는 알파벳의 개수가 25개('E'를 제외하고)이므로, 잘 생각해보면 O(n^2 * 25)에도 풀 수 있을 것 같습니다.
skeksk91 9년 전
AABBB
BBAAA
이고 A가 100점 B가 200점이면
100 100 200 200 200
200 200 100 100 100
이런 식으로 정수로 배열을 만든 후에 탐색을 하였습니다.
작은예제는 해결가능한데, 제출하면 런타임 오류 뜨군요 ㅠ
10^6 만큼 재귀호출하는데 스택오버플로가 난건가요?
아니면 pruning을 해야하는 그런 문제인가요.
아니면 아예 다른 방식이 필요한가요 아니면 반복문으로도 해결?그건 좀 어렵겠는데 ㅠ
요번 연습대회때 이것만 10번넘게 고치다가 ㅋㅋㅋ 시간 다갔네요 ㅠㅠ