[백준/Python] 1261 알고스팟

문제는 여기

코드

import sys
from collections import deque
input = sys.stdin.readline
n, m = map(int, input().split())

graph = []

for i in range(m):
    graph.append(list(map(int, input().strip())))

dist = [[-1] * n for _ in range(m)]

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

def bfs(a,b):
    queue = deque()
    queue.append((a,b))
    dist[0][0] = 0

    while queue:
        x,y = queue.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < m and 0 <= ny < n:
                if dist[nx][ny] == -1: # 방문 안한 경우만
                    if graph[nx][ny] == 0: # 벽이 없는 경우만
                        dist[nx][ny] = dist[x][y]
                        queue.appendleft((nx,ny))
                    else:
                        dist[nx][ny] = dist[x][y] + 1
                        queue.append((nx,ny))

bfs(0,0)
print(dist[m-1][n-1])

기록할 점

이 문제는 못풀고 구글링에 의존했다
bfs/dfs 문제를 풀다보면 벽을 최소한으로 뚫는 문제들을 볼 수 있는데
방법을 알아두는게 좋을 것 같다.

포인트는 벽이 없는 곳을 우선으로 가고 벽이 있는 곳을 나중에 가는 것
벽이 있는 곳을 가게된다면 벽이 있는 곳에 몇 번 갔는지 기록해두는 변수에 +1을 해준다
미로만들기 문제와 거의 똑같다