[백준 파이썬] 2206 벽 부수고 이동하기

📌문제 출처

백준 단계별 문제풀이 - 그래프와 순회
https://www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

❓ 문제

 

 

❗ 풀이

• bfs 응용(3차원 방문 확인)

📗 풀이 코드

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

def bfs():
    stack = deque([[1,0,0,0]])
    while stack :
        cnt,y,x,crashed = stack.popleft()
        if y==n-1 and x==m-1 : # 도착했다면 반환
            return cnt # 도착 칸 수
        cnt += 1
        for i in range(4):
            ny,nx=y+dy[i],x+dx[i]
            if 0<=ny<n and 0<=nx<m and not visited[ny][nx][crashed] :
                if maps[ny][nx] == 1 and not crashed :# 벽이고 부순 적이 없다면
                    visited[ny][nx][1] = 1 # 벽 부수고 방문
                    stack.append([cnt,ny,nx,1]) # 이동칸수,y,x,crashed stack에 넣기
                elif not maps[ny][nx] : # 벽이 아니라면
                    visited[ny][nx][crashed] = 1 # 벽 안부수고 방문
                    stack.append([cnt,ny,nx,crashed]) # 이동칸수,y,x,crashed stack에 넣기
    return -1

n,m = map(int,input().split())
maps = [list(map(int,list(input().strip()))) for _ in range(n)]
visited = [[[0]*2 for _ in range(m)] for _ in range(n)] # [y][x][0]은 안뚫 방문 [y][x][1]은 벽뚫방문
visited[0][0][0]=1 # 첫번째 칸 방문 이력 추가
dx,dy = [0,0,-1,1], [-1,1,0,0]
print(bfs())

📗 코드 해설

• 2차원 bfs라면 방문확인하는 visited는 2차원이면 충분하지만 이번 문제에는 해당 칸에서 벽을 부수고 지나가는 경로인지 부수지 않고 지나가는 경로인지를 확인하기 위해 3차원으로 넣어준다.
  이때 특정 칸(x,y)의 visited[y][x]에 따른 경우를 확인해보자
  - visited[x][y] = [0,0] : 아직 방문을 하지 않음
  - visited[x][y] = [1,0] : 이 칸에 방문할 때까지는 벽을 부수지 않음
  - visited[x][y] = [0,1] : 이 칸에 방문하기 이전에 벽을 부순 적이 있거나 이 칸에 방문하기 위해 벽을 부숨
  - visited[x][y] = [1,1] : 이 칸에 벽을 안 부수는 경로로도, 벽을 부수는 경로로도 방문한 적이 있음
  방문확인이 1로 되어있다고 해서 이 칸에 도달해서 벽을 부순 것이 아니라 이미 벽을 부순 경로로 지나고 있다는 것을 주의해야한다.
• 첫번째 칸에 최초 시작할 때 방문 이력을 넣어주지 않으면 bfs 내에서 재방문 할 수 있기에 1을 넣어주고 시작한다.
• stack에는 cnt(밟아온 칸수),  y, x, crashed(벽을 부순 경험) 을 넣어둔다.
• 만약에 도착지점이라면 그대로 cnt를 반환(한 칸씩 이동하므로 제일 먼저 도착지점에 다다르면 이동횟수가 제일 적다)
• 이동할 수 있고 방문한 적이 없는 상하좌우 칸을 돌며 확인한다.
  - 벽에 도달했으나 부순 적이 없으면 => 벽을 부수고 진행, 이때 crashed는 1로 바뀌며 visited[x][y][1] = 1이 된다.
  - 벽이 아니라면 => 그대로 진행, 이때 crashed는 지금까지 가져온 상태를 유지하며 visited[x][y][crashed] = 1이 된다.
• while문을 모두 반복해도 도착하지 않는다면 도달할 수 없으므로 -1을 반환한다.