[BFS] 백준 2206번 : 벽 부수고 이동하기 - 파이썬 Python

 

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

 

 

생각하기

미로 찾기와 비슷한 게임이라고 판단하여 BFS를 사용하여 마지막 정점까지 가는 최소를 구하기로 생각했다

미로 찾기 문제와 달리 까다로운 해결해야할 조건 하나는

"벽을 한개 깰 수 있다는 점"

 

각 정점에서 다른 정점으로 이동하는 경우는 다음과 같다

• 빈칸 -> 빈칸 : 벽 깨기 유무와 상관 없이 모두 이동 가능
• 빈칸 -> 벽 : 벽 깨지 않은 경우 만 이동 가능 / 벽을 깬 경우 이동 불가
• 벽 -> 벽 : 이동 불가
• 벽 -> 빈칸 : 벽 깨기 유무와 상관 없이 모두 이동 가능

 

백준 강의에서 정점이란

정점은 앞에 어떤 상황이건 간선에 대하여 항상 같은 일을 해야 함

이 정의가 지켜져야 정점이라는 것이 성립한다

 

따라서 큐에 넣어주는 정점의 형태를 조금 다르게 정의해야 한다

 

정점 ( row, col, 이동 횟수, 벽 파괴 유무)

 

이렇게 정점을 정의하여 앞에 어떤 상황이건 벽 파괴 유무 를 통해 파악하여 대처할 수 있다

 

 

구현하기

BFS를 하려면 방문하지 않은 정점에 대해서만 방문을 해야 하는데

이번에는 경우가 두가지가 있다

• 벽을 아직 깨지 않았을 때 파생되는 경우
• 벽을 깬 후에 파생되는 경우

이에 대해서는 3차원 리스트를 만들어서 진행한다

최소 이동횟수를 구하는 과정이기 때문에 3차원 리스트는 1억으로 초기화한다

 

 

from collections import deque
import sys
input = sys.stdin.readline
max_num = int(1e9)

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

visited = [[[max_num for col in range(M)] for row in range(N)] for depth in range(2)]
# visited[row][col][0] : 벽 1회 깨기 전의 방문 최소 cnt 횟수
# visited[row][col][1] : 벽 1회 꺠기 후의 방문 최소 cnt 횟수


data = []

for _ in range(N):
    data.append(list(map(int, input().strip())))




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


# (0, 0)부터 시작해서 (N-1, M-1) 까지 가는 것으로
q = deque()


def bfs(col, row, cnt):

    q.append((col, row, cnt, False))
    visited[0][col][row] = cnt

    while q:

        cur = q.popleft()
        
        for d in range(4):
            ny = cur[0] + dy[d]
            nx = cur[1] + dx[d]

            if ny<0 or ny>=N or nx<0 or nx>=M:
                continue

            if ny == N-1 and nx == M-1:
                if cur[3] == False:
                    visited[0][ny][nx] = min(visited[0][ny][nx], cur[2]+1)
                else:
                    visited[1][ny][nx]= min(visited[1][ny][nx], cur[2]+1)

                continue

            
            # 1번 벽 깨기를 하지 않은 경우
            if cur[3] == False:
                # 1번도 벽깨기 안한 경우, 벽을 만나면 방문하지 않은 벽일 경우 깨기
                if data[ny][nx] == 1 and visited[1][ny][nx] == int(1e9):
                    visited[1][ny][nx] = cur[2]+1
                    q.append((ny, nx, cur[2]+1, True))
                
                # 1번도 벽깨기 안한 경우, 빈칸을 만나면 방문하지 않은 경우 진입
                if data[ny][nx] == 0 and visited[0][ny][nx] == int(1e9):
                    visited[0][ny][nx] = cur[2]+1
                    q.append((ny, nx, cur[2]+1, False))

            # 1번 이상 벽깨기를 한 후인 경우
            else:
                # 1번 이상 벽꺠기를 한 경우, 빈칸을 만나면 진행
                if data[ny][nx] == 0 and visited[1][ny][nx] == int(1e9):
                    visited[1][ny][nx] = cur[2]+1
                    q.append((ny, nx, cur[2]+1, True))

                # 1번이상 벽깨기 한 경우, 빈칸 아닌거 만나면 진행 X


    return min(visited[0][N-1][M-1], visited[1][N-1][M-1])

result = bfs(0, 0, 1)
if result == int(1e9):
    print(-1)
else:
    print(result)