[알고리즘] 백준 2206번 Python

ㅓ

 

분류

BFS

혼자 힘으로 해결 했는가?

O

느낀 점

매우 모범적인 문제라고 생각한다.

 

기계적으로 BFS를 막 때려맞히는 것이 아니라, BFS의 근본적인 목적 = 그래프 탐색을 이해하고 있는지 스스로

점검을 하기 좋은 문제라고 생각이 된다.

 

가중치가 모두 동일한 그래프에서 특정 지점에서 특정 지점으로의 최단 경로를 찾을 때 가장 빠른 알고리즘이 BFS이다.

최단경로를 찾는 알고리즘으로는

 

다익스트라 알고리즘

플로이드 와샬 알고리즘

벨만 포드 알고리즘

 

이렇게 존재하고 저 셋중 가장 빠른 것은 우선순위 큐를 사용한 다익스트라 알고리즘이다. O(Nlogn)

 

다익스트라 알고리즘은 가중치가 여러개인 경우 사용할 수 있는 가장 빠른 알고리즘이나

가중치가 모두 같다면, BFS가 가장 빠르다 O(N)

 

BFS는 사실 최단경로를 찾기위해 탄생한 알고리즘은 아니고, 그래프를 탐색하는 알고리즘이다.

 

그러나 BFS는 하나의 지점에서 도달 가능한 지점들을 Depth별로 탐색을 하기 때문에

각 지점에 도달 가능한 가중치가 같을 경우 최단경로를 찾기 적합한 알고리즘이 된다.

 

아무튼 이번 문제도 살펴보면 이동함에 있어서 모두 1초가 걸린다.

 

즉, 가중치가 모두 같다.

 

그리고 사실 이 문제는 주어진 필드를 탐색한다기 보다는,

각 좌표마다 벽을 부쉈는지, 안 부쉈는지를 나타내는 상태공간 트리를 탐색한다고 볼 수 있다.

 

이러한 문제를 해결함에 있어서 이동의 주체가 매 순간마다 가진 상태에 대한 트리를 탐색한다고 볼 수 있다.

 

처음 이 문제를 접했을 때, 단순히 visit table을 2차원으로 두고, 벽을 부쉈는지를 변수로 배치했다.

 

이는 곧 BFS를 사용한다는 느낌 보다는 그저 문제 풀이를 외우고 그대로 따라한 느낌이다.

 

그러나 저 방식대로 하면 문제가 생긴다.

---

 

시작지점 0,0에서 (y1,x1)에 도달 시, 벽을 부수게 되고 벽을 부쉈다는 변수를 0으로 둔다.

 

이후 (y2, x2)에 도달 시 벽을 부쉈다는 변수를 확인하겠지만, 해당 좌표에 도달하는 경로가  여러가지가 가능할 것이다.

 

그렇다면 변수가 이미 0이 되어버린 이상, (x2, y2)에 도달 가능한 상태가 모두 벽을 부쉈다는 정보로 덮어씌워진다.

 

따라서 이를 방지하기 위해서는 모든 좌표마다 벽을 부쉈는지를 둬야하고

 

이는 곧 차원을 하나 더 늘려 z축을 두게 되는 것과 동일하다.

 

따라서 이 문제는 3차원을 둬야하고 서로 종속되는 상태 3가지를 표현하며 탐색을 해야한다.

 

---

내가 작성한 코드

from sys import stdin
from collections import deque

N, M = map(int, input().split())

board = []
MX = 10000001

for i in range(N):
    board.append(list(stdin.readline().rstrip()))

# N, M 좌표에 벽을 부수고 온 경우인지, 아닌지
timeStamp = [[[MX for _ in range(2)] for Col in range(M)] for Row in range(N)]


# 초기 시작 점은 무조건 고정, (0,0)
# (0,0)에서는 벽을 부수지 않은 상태에서 있음, 그리고 그래프가 0이면 타임스탬프 그래프의 z축 1에 값이 있어선 안됨

# 큐에서 뽑았을때, 벽을 부순 상태이면 다음 탐색 시 벽을 부술 수 있어도 부수면 안됨

move = deque()

timeStamp[0][0][0] = 1

move.append((0,0,0,1))

dy = [-1,1,0,0]
dx = [0,0,-1,1]

def solve():

    while move:
        y, x,z, time = move.popleft()

        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]

            if 0 <= ny < N and 0 <= nx < M and timeStamp[ny][nx][z] == MX:
                # 벽인지 체크
                if board[ny][nx] == '1':
                    # 벽을 부순 후, 즉 z축이 1인지체크
                    if z == 1:
                        continue
                    # 해당 좌표를 벽을 부수지 않고 방문한적이 있다면 역시 무시해야함
                    if timeStamp[ny][nx][0] != MX:
                        continue
                    else:
                        # 벽을 부수고 가본다
                        timeStamp[ny][nx][1] = time + 1
                        move.append((ny,nx,1, time + 1))
                else:
                    # 벽이 아니면 기존 z축 그대로 진행함
                    timeStamp[ny][nx][z] = time + 1
                    move.append((ny,nx,z,time + 1))


solve()


if timeStamp[N - 1][M - 1][0] != MX or timeStamp[N - 1][M - 1][1] != MX:
    print(min(timeStamp[N - 1][M - 1][0], timeStamp[N- 1][M - 1][1]))
else:
    print(-1)

 

 

 

---

비슷한 문제들

 

https://www.acmicpc.net/problem/17836

17836번: 공주님을 구해라!