미로찾기 - DFS(Stack)

Stack

Stack은 Last in, First out구조로 가장 늦게 들어간 데이터가 가장 먼저 나오는 구조이다.

Insert/Delete만 제공하고 각각 Push/Pop이라고 부른다.

위키백과

성능

Push: O(1)

Pop: O(1)

간단한 구현

Stack을 이용한 미로찾기

1. 현재 위치에서 주변에 갈 수 있는 위치 중 하나로 이동하면서 이전에 있던 위치를 Stack에 Push한다.

2. 현재 위치에서 주변에 갈 수 있는 위치가 없으면 Stack에서 Pop해서 이전 위치로 돌아간다.

3. 현재 갈 수 있는 곳이 없으며 Stack이 비어있으면 미로찾기에 실패한다.

4. 오른쪽 맨 아래에 도착하면 성공한다.

DFS 미로찾기의 정확성

• (0, 0)에서 어떤 위치 (s,t)로 가는 길이 있다고 가정한다.
• (0,0) -> (a1,b1) -> ... -> (s,t)인 좌표 sequence있다.

만약 (s,t)를 방문하지 않는다고 가정하면 (0,0) -> (a1,b1) -> ... ->(s,t)사이에 가본 (p,q)가 있을 것이고 안가본 (i,j)가 있을 것이다.

 

위의 알고리즘을 보면 Stack이 비었을 때 종료하기 때문에 전진한 모든 곳에서 후진을 해야한다.

하지만 전진할 곳이 없어야만 후진을 한다. 따라서 전진할 수 있는 (i,j)가 있는데 방문하지 않는 다는 사실은 모순이된다.

 

성능

한 칸에서 일어나는 일들을 따로 생각해보면

1. 한칸 당 최대 7번 전진 할 수 있다. (이전의 위치와 현재 위치를 제외하면 총 7번)
2. 후진은 1번만 가능하다.
3. 따라서 총에서 O(MN)시간이 걸린다.