미로 탐색
-
모각코PS / 백준 2178 미로 탐색PS 2022. 6. 11. 16:32
모각코 PS스터디 그래프 탐색 두 번째 문제인 '미로 탐색'입니다. 문제의 제약조건을 보면서 어떤 알고리즘으로 접근하면 좋을지 힌트를 얻을 수 있기도 하죠? 표본 수가 적고, 시간 제한이나 메모리가 상대적으로 넉넉하고, 좌표나 맵 같은 것이 주어지면 그래프가 떠오르는 것 같습니다. 그리고 각 탐색로의 길이를 비교하거나, 특히 가장 빠른 탐색 경로를 찾아야 하는 경우에는 BFS를 선택하는 편이 '대개' 유리하겠죠. 모든 경로를 다 들어가보고 길이를 기록해뒀다가 제일 짧은 길이를 리턴하는 것보다, 모든 경로를 동시에 진행하다가 한 경로가 끝에 다다르면 나머지를 더이상 탐색하지 않고 리턴하는게, 탐색 횟수가 훨씬 적을 거니까요. 이번 문제가 그런 스타일의 문제였습니다. 문제와 풀이..