[BOJ] (BFS) 1261번 알고스팟

흔한 미로에서 BFS를 이용하여 해결하는 문제다.

특이한 점은, 목적지까지의 최소경로 이런게 아니라, 벽을 최소 몇개 부숴야 하는가 였다.

즉, 1을 최소한으로 지나갈 수 있는 경우를 구하는 것이다.

 

우리는 지나간 경로를 세는게 아니라, 지금까지 만난 1의 개수를 세서 저장하면 되는 것이다. 

ans라는 미로와 크기가 같은 2차원 배열을 만들고, 1을 더 지나서 온 경로는 무시하고, 더 작은 경로만 카운트한걸 저장하면 된다. 

그렇게 해서 정답은 ans[n-1][m-1]이 되는 것.

 

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

board = [list(map(int, list(input().rstrip()))) for _ in range(n)]
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
q = deque()
q.append((0, 0, 0))
ans = [[1e9]*m for _ in range(n)]
ans[0][0] = 0

def solve():
    while q:
        x, y, cnt = q.popleft()
        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            
            if not (0<=nx<n and 0<=ny<m):
                continue
            
            if board[nx][ny] == 0 and ans[nx][ny] > cnt:
                q.append((nx, ny, cnt))
                ans[nx][ny] = cnt
            
            elif board[nx][ny] == 1 and ans[nx][ny] > cnt+1:
                q.append((nx, ny, cnt+1))
                ans[nx][ny] = cnt+1
                
    print(ans[n-1][m-1])
    
solve()

 

 

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

1261번: 알고스팟