2178 - 미로탈출

문제 요약

1. Input으로 미로가 들어온다. (1은 이동할 수 있는 칸, 0은 이동할 수 없는 칸)
2. 미로의 좌측 상단(0, 0)에서 우측 하단(n, m)으로 이동할 때 몇칸을 지나가야 하는가?

접근법

지난번에는 DFS와 BFS의 아주 기초적인 문제를 살펴보았다. 이번 문제 역시 BFS를 활용하는 문제로 단순히 그래프를 탐색하는 것이 아니라 좀더 응용된 버전이다. 그러나 걱정할 필요는 없다. 아직은 BFS 문제중 매우 쉬운 문제에 속하고 BFS는 결국 풀이 방법이 다 비슷비슷하기 때문에 BFS 문제를 여러번 풀어보면 결국 대부분의 문제를 쉽게 풀수 있다. 만약 이 문제가 어렵게 느껴졌다면, 아직 BFS에 익숙하지 않아서 그런것이라고 생각한다.

이 문제에서의 시작점은 (0, 0)이다. 만약 (1, 0)과 (0, 1)이 모두 1이라면 (0, 0)에서 이동할 수 있는 좌표는 (1, 0), (0, 1)이 된다. 즉 1번의 이동으로는 (1, 0), (0, 1) 좌표로 이동할 수 있다는 것을 의미한다. 2번째 이동으로 갈수 있는 좌표는 (1, 0), (0, 1)에서 갈수 있는 좌표를 의미하므로 (2, 0), (1, 1), (0, 2), (0, 0)이 된다. 그러나 (0, 0)은 이미 방문했던 좌표이기 때문에 다시 방문을 하면 (0, 0) <-> (1, 0), (0, 1)로 이동하는 무한 루프에 빠질 수 있다. 따라서 한번 방문한 좌표는 다시 방문하지 않도록 방문했던 좌표를 기록하는것 또한 필요하다. 이미 방문한 (0, 0)을 제외하면 2번의 이동으로 갈 수 있는 좌표는 (2, 0), (1, 1), (0, 2) 세개의 좌표가 된다.

위의 설명은 미로가 전부 1이라는 가정을 하고 있다. 만약 0이 있다면 해당 좌표로는 이동할 수 없다. 즉 예제입력 1에서 (0, 1)은 0이기 때문에 1번의 이동으로 갈 수 있는 좌표는 (1, 0)이 된다. 위와 같은 과정을 반복하면서 몇번의 이동만에 (n, m) 좌표를 방문할 수 있는지 체크하면 문제는 쉽게 해결된다. 결국 그래프를 탐색하는 문제는 아니었지만 그래프를 탐색하는 문제와 같은 방법으로 문제를 해결할 수 있었다. BFS 문제를 계속해서 풀다보면 위와 같은 풀이가 더욱더 익숙해질 것이라고 생각한다.

Source Code

소스코드 보러가기

• 아직 주석이 달려있지 않습니다.
• pseudocode 보다는 python 코드를 올릴 예정입니다.
• Code Review는 언제나 환영합니다 (코드를 더 깔끔하게, 효율적으로 만드는걸 도와주세요!)