boj2206 - 벽 부수고 이동하기

문제

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

코드

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

row, col = map(int, input().split())
graph= [list(map(int, input().rstrip())) for _ in range(row)]
visit = [[[0]*2 for _ in range(col)] for _ in range(row)]
# print(graph)

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

def bfs(x,y, c):
    wall = 0
    q = deque()
    q.append((x,y,0))
    visit[x][y][wall] = c
    while q:
        x,y,wall= q.popleft()
        if x == row-1 and y == col-1:
            return visit[x][y][wall]

        for k in range(4):
            tx = x+dx[k]
            ty = y+dy[k]
            if 0<=tx<row and 0<=ty<col and visit[tx][ty][wall] == 0:
                # 벽이 아니면 이동, 이전 비용 + 1 저장
                if graph[tx][ty] == 0:
                    visit[tx][ty][wall] = visit[x][y][wall]+1
                    q.append((tx,ty,wall))
                # 한번도 벽 뚫은적 없고, 다음 경로가 벽이면 벽 뚫은 후의 visit 에 비용 저장
                if wall == 0 and graph[tx][ty] == 1:
                    q.append((tx,ty,1))
                    visit[tx][ty][1] = visit[x][y][wall]+1
    return -1

print(bfs(0,0,1))
# print(visit)

설명

visit 배열을 3차원으로 만들어 벽은 부수기 전/후를 체크(wall)하고 , visit[tx][ty][wall] 에 비용을 저장하는 것이 포인트..어렵다