백준 2206(벽 부수고 이동하기) - python

접근

문제를 보고 일반적인 그래프 탐색 문제라고 생각했다. 여기서 어려웠던점은 벽을 한개까지 부술수있다는 점인데 이 부분이 너무 까다롭다고 느껴졌다. 처음 생각은 bfs를 한번 돌리고 그러면서 닿는 벽들의 좌표를 set에 저장하고 벽을 빼고 넣으면서 계속 bfs를 돌리려는 생각을 했다. 또 두번째 생각은 처음과 끝에서 bfs를 돌려서 각각 맞닿는 벽을 set에 저장하고 이 두 set의 교집합을 통해 뺄 벽을 정하는 방법을 생각했다. 하지만 두 방법 모두 시간이 오래걸려 결국 실패했다. 그리고 마지막에 할 수 있었던 생각이 visit을 3차원으로 만드는 것이었다. bfs는 각 visit[i][j][0] 가 있다면 항상 가장 빠르게 도달하는 횟수가 visit[i][j][0]에 저장된다. visit[y][x][1]이 벽을 한번 부수고 해당 y,x까지 가는데 걸리는 cost라고 생각하자. y,x는 벽이고 아직 도착하지 않은 좌표이다. y+1,x 이 밑으로 한칸 움직이면 y,x이 된다.이때 y+1,x 이 벽을 부순 횟수가 0이라면 visit[y][x][1] = visit[y-1][x][0] +1 을 해주면 벽을 한번 부수고 해당 y,x까지 가는 최소 비용이 된다. 그 이전에 벽을 한번 부수고 그 좌표까지 더 빠르게 도달할 수 있는 경우가 있었다면, 미리 체크될 것이다.

0000

1 1 10

01 00 

이 map에서 3행1열까지 벽을 1번 부수고 이동하는 최소값에 대해 생각해보면 i,j가 0,0 이고 상하좌우로 이동하며 visit[1][0][1] = 2 가되고 여기서 한번 더 움직이면 3이된다. 이 경로 말고 3행 2열을 부수고 3행 1열을 하는 방법도 있지만 이미 이때는 최소 경로로 3이 체크되어서 값이 갱신되지 않는 것이다.

 

나의코드

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

ty, tx = map(int,input().split())

M = [list(map(int,input().rstrip())) for _ in range(ty)]

d = [(1,0),(-1,0),(0,1),(0,-1)]

def dfs(i,j,k):
    distance = [[[0,0] for _ in range(tx)] for _ in range(ty)]
    distance[i][j][k] = 1
    queue = deque()
    queue.append((i,j,k))
    while queue:
        y,x,z = queue.popleft()
        if y == ty-1 and x == tx-1:
            break
        for dy, dx in d:
            ny = y + dy
            nx = x + dx
            if 0<=ny<ty and 0<=nx<tx:
                if not distance[ny][nx][z]:
                    if M[ny][nx] == 0:
                        distance[ny][nx][z] = distance[y][x][z]+1
                        queue.append((ny,nx,z))
                    else:
                        if z == 0:
                            distance[ny][nx][z+1] = distance[y][x][z]+1
                            queue.append((ny,nx,z+1))
    return distance[ty-1][tx-1][z]


r = dfs(0,0,0)
if r==0:
    print(-1)
else:
    print(r)