[BOJ][Python]2206 풀이

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

2206번: 벽 부수고 이동하기

from collections import deque
import sys
ssr = sys.stdin.readline

INF = 1000001

def bfs():
    dpos = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    visited = [[0 for _ in range(m)] for _ in range(n)]
    visited[0][0] = 1
    q = deque([(0, 0, 0, 0)])
    ans = INF
    while q:
        r, c, distance, break_wall = q.popleft()
        if r == n-1 and c == m-1:
            ans = min(ans, distance)
        for dr, dc in dpos:
            if 0 <= r+dr < n and 0 <= c+dc < m: # 이동할 위치가 보드 위일 때
                if break_wall == 1: # 벽을 뚫은 경로라면
                    if visited[r+dr][c+dc] == 0: # 벽을 뚫었으니까 방문 0 일때만 가능
                        if board[r+dr][c+dc] == '0': # 벽 더 못뚫으니까 길만
                            q.append((r+dr, c+dc, distance+1, 1))
                            visited[r+dr][c+dc] = 1
                else: # 벽을 뚫은 적 없는 경로라면
                    if visited[r+dr][c+dc] < 2: # 미방문이거나 벽을 뚫고 방문한 적 있거나
                        if board[r+dr][c+dc] == '0': # 길이면
                            q.append((r+dr, c+dc, distance+1, 0))
                            visited[r+dr][c+dc] = 2
                        else: # 벽이면
                            q.append((r+dr, c+dc, distance+1, 1))
                            visited[r+dr][c+dc] = 1
    return ans+1 if ans != INF else -1
                        
n, m = map(int, ssr().split())
board = [ssr().rstrip() for _ in range(n)]
print(bfs())

 

 

이번에는 사실 아이디어는 금방 떠올랐는데 구현 능력이 조금 부족했던 것 같습니다. 벽을 뚫었는지 안뚫었는지를 모든 경우의 수에 따라 판단했다간 (1000*1000)^2 만큼 연산을 해야해서 브루트포스는 패스하구요. 예전에 길이도 함께 담아서 bfs를 진행한다 어쩐다 하는 얘기를 다른 포스팅에서 했었는데요. 그것과 비슷하게 벽을 뚫고 진행 중인 경로인지 아닌지도 함께 담아서 큐에 저장하면 되겠다는 생각이 드는 것 까지는 순식간이었습니다. 다만 그 뒤에 구현을 하는 부분에서는 조금 고민을 많이 했네요.

 

단순하게 방문 처리를 bool 타입으로 할 경우에 해당 경로가 최단 거리가 아님에도 불구하고 못하는 경우가 있을 수 있습니다. 예를 들어 처음에 조금 돌아가더라도 후반부에 벽을 한 번 뚫는게 실제 해라고 가정했을 때, 처음에 벽을 뚫었기 때문에 나중에 벽을 못뚫어서 훨씬 둘러가는 길이 실제로 최단거리가 될 수 없는데도 이미 방문처리를 다 하고 돌아다녀서 정답을 출력하지 못하는 경우가 있을 수 있겠죠. 이것과 비슷하게 아예 목적지 바로 앞에서 무조건 벽을 뚫어야 하는데 이미 앞에서 벽을 뚫었던 경로가 방문처리를 먼저 했을 수도 있구요.

 

그래서 방문처리를 할 때 벽을 뚫고 진행하는 경우와 벽을 뚫지 않고 진행하는 경우를 구분해줘야 했습니다. 저는 벽을 뚫었으면 1, 벽을 안뚫었으면 2로 해서 구분을 했고, 벽을 뚫은 경우는 아직 방문한 적이 없는 위치만 갈 수 있고, 벽을 아직 안뚫은 경우는 방문한 적 없거나 벽을 뚫고 방문한 적이 있는 경우 둘 다 갈 수 있도록 해주었습니다.

 

일단은 조건에 맞으면 큐에 저장할 것이기 때문에 딱히 같은 위치에 대한 정보를 두 번 저장해도 상관은 없고, 벽을 이미 뚫은 경우는 벽을 더 뚫을 수 없으니 장래성이 없다고 판단했고, 벽을 아직 뚫지 않은 경우는 설령 벽을 뚫고 지나가는 경로가 이미 방문했던 곳이라도 나중에 벽을 뚫으면서 최단거리가 될 수 있기 때문에 이렇게 해주었습니다. 딱히 벽을 먼저 뚫고 지나온 쪽이 더 빨라도 상관없습니다. ans에 저장할 때 더 작은 값을 저장하도록 해놓았기 때문에 결과에 영향은 미치지 않아요.

 

좀 아쉬운 건 파이썬 런타임 1위 코드가 300ms대의 기록을 보여줘서 어떤 코드인지 너무 보고 싶은데 비공개로 해두셔서 볼 수 없다는게 좀 아쉽네요.