[백준] 2206번 - 벽 부수고 이동하기 (파이썬)

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

# 벽 부수고 이동하기
import sys
from collections import deque
input = sys.stdin.readline
N, M = map(int, input().split())
arr = []
for i in range(N):
    arr.append(list(map(int, input().strip())))
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]


def bfs():
    global result
    q = deque()
    q.append((0, 0, 0))
    time = [[[0] * 2 for _ in range(M)] for _ in range(N)]
    time[0][0][0] = 1
    while q:
        x, y, wall = q.popleft()
        if x == N-1 and y == M-1:
            return time[x][y][wall]
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            if 0 <= nx < N and 0 <= ny < M:
                if arr[nx][ny] == 1 and wall == 0:
                    time[nx][ny][wall+1] = time[x][y][wall] + 1
                    q.append((nx, ny, wall+1))
                elif arr[nx][ny] == 0 and time[nx][ny][wall] == 0:
                    time[nx][ny][wall] = time[x][y][wall] + 1
                    q.append((nx, ny, wall))


result = bfs()
if result:
    print(result)
else:
    print(-1)

 

BFS

1. q에 초기값을 놓고 q가 빌 때까지

  - arr의 다음 위치가 벽(1)이고 현재 벽을 뚫은 횟수(wall)이 0이면 wall+1

  - arr의 다음위치가 길(0)이고 방문하지 않았다면 wall그대로 유지하고 시간만 증가

2. 마지막 리스트의 값을 리턴

 

한 번 벽을 부술 수 있기 때문에 3차원 리스트를 이용해서 벽을 부쉈을 때 1, 벽을 부수지 않았을 때 0으로 생각해서 풀었다

시간초과를 피하기 위해서는 3차원 리스트로 상태 관리를 해줘야 한다