[BOJ]17090번: 미로 탈출하기

 

문제: https://www.acmicpc.net/problem/17090

---

TOP-DOWN 방식 DP로 풀고 시간초과가 나서 다르게 접근한 문제입니다.

 

문제가 되는 상황은 싸이클이 발생하는 상황을 어떻게 처리하느냐입니다.

 

해결 방법은

 

1. 기저사례 칸 좌표를 모두 큐에 넣습니다. 

기저사례 칸이라 함은 현재 칸에서 주어진 방향으로 점프하면 밖으로 나가는 좌표를 의미합니다.

 

2. 큐에 들어가 있는 좌표에서 인접한 UDLR 방향 네 개의 좌표를 탐색합니다.

인접한 좌표 중에, 인접한 좌표 -> 기저 사례 칸으로 점프하는 인접한 좌표를 새로 큐에 넣습니다.

(이 인접한 좌표가 다시 기저 사례 칸이 되는 방식입니다.)

 

3. BFS방식으로 방문 표시를 하면서 2번을 반복하며 기저 사례칸과 연결되는 모든 칸을 세주면 됩니다.

O(NM)에 해결이 가능합니다.

---

코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ17090.cc