[백준/Python]2206_벽 부수고 이동하기

문제

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

2206번: 벽 부수고 이동하기

풀이

BFS와 3차원 배열을 사용했습니다.

최단 거리를 저장할 3차원 배열 visited를 선언하고 0으로 초기화 합니다.(visited[0][0][1] = 1)

smash가 1일 경우 벽을 뚫을 수 있는 상태라는 것을 나타냅니다.

 

1. 큐에서 popleft한 값이 벽일 경우(1)
   1. smash가 1일 때
      
      • 벽을 부수고 smash를 0으로 변경하여 큐에 푸쉬하고, visited[yy][xx][0] 갱신
   2. smash가 0일 때
      • continue
2. 큐에서 popleft한 값이 벽이 아닐 경우(0)
   • 큐에 푸쉬하고 visited[yy][xx][smash] 갱신

코드

import sys
from collections import deque


def bfs():
    q = deque([(0, 0, 1)])
    visited = [[[0] * 2 for _ in range(m)] for _ in range(n)]
    visited[0][0][1] = 1
    while q:
        y, x, smash = q.popleft()  # smash가 1이면 벽을 뚫을 수 있다
        if y == n - 1 and x == m - 1:
            return visited[y][x][smash]
        for i in range(4):
            yy = y + dy[i]
            xx = x + dx[i]
            if 0 <= yy < n and 0 <= xx < m:
                if matrix[yy][xx] == 1 and smash == 1:
                    visited[yy][xx][0] = visited[y][x][1] + 1
                    q.append((yy, xx, 0))
                elif matrix[yy][xx] == 0 and visited[yy][xx][smash] == 0:
                    visited[yy][xx][smash] = visited[y][x][smash] + 1
                    q.append((yy, xx, smash))
    return -1


n, m = map(int, sys.stdin.readline().rstrip().split())
matrix = []
for _ in range(n):
    s = list(map(int, list(sys.stdin.readline().rstrip())))
    matrix.append(s)

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

print(bfs())