[Python] BOJ 2206 - 벽 부수고 이동하기

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

2206번: 벽 부수고 이동하기

# 3차원 visited배열을 이용한 bfs문제이다.

 

# visited배열을 3차원으로 선언해 벽을 부셨을때는 visited[1][x][y],

   안 부셨을 때는 visited[0][x][y] 이런식으로 저장해주었다.

 

# bfs함수: 현재 좌표가 도착지점이라면 visited[b][x][y]를 return해준다.

 

              일반 bfs함수처럼 상하좌우를 탐색하는데,

              m[nx][ny]가 0일때는 visited[b][nx][ny] = visited[b][x][y] + 1을 해주고

             

              m[nx][ny]가 1일때는 b가 0이어야 벽을 부술 수 있으므로 

              visited[1][nx][ny] = visited[b][x][y] + 1을 해준다.

              그리고 q에 넣을 때 (b+1, nx, ny)를 넣어준다.

 

              q의 모든 원소를 돌았을때까지 마지막지점에 도착 못했으면 -1을 return해준다.

 

 

import sys
from collections import deque
input = sys.stdin.readline
N, M = map(int,input().split())
m = [list(input().rstrip()) for _ in range(N)]
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
visited = [[[0] * M for _ in range(N)] for _ in range(2)]
q = deque()

def bfs():
    q.append((0, 0, 0))  # 벽 부순지여부, x좌표, y좌표
    visited[0][0][0] = 1
    while q:
        b, x, y = q.popleft()
        if (x, y) == (N-1, M-1):
            return visited[b][x][y]
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < N and 0 <= ny < M and not visited[b][nx][ny]:
                if m[nx][ny] == '0':
                    visited[b][nx][ny] = visited[b][x][y] + 1
                    q.append((b, nx,ny))
                if m[nx][ny] == '1' and b == 0:
                    visited[1][nx][ny] = visited[b][x][y] + 1
                    q.append((b+1, nx, ny))
    return -1

print(bfs())

(solved.ac 티어: 골드 4)