문제 링크

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

문제 설명

• board가 주어짐
• 벽을 부수며 (n,m)으로 갈 때, 벽을 부순 횟수의 최솟값 출력

풀이

• bfs 반복하면서 벽 부수기
• 노드 개수 N일 때, O(N^2) -> 10000^2

파이썬 코드

import sys
from collections import deque


def solution():
    read = sys.stdin.readline
    w, h = map(int, read().split())
    board = [list(read().rstrip()) for _ in range(h)]
    count = [[float('inf')] * w for _ in range(h)]
    count[0][0] = 0

    num = 1
    while True:
        finished = bfs(num, w, h, board, count)
        if finished:
            break
        num += 1

    print(num-1)


def bfs(num, w, h, board, count):
    dy, dx = [0, 0, 1, -1], [1, -1, 0, 0]
    visited = [[0] * w for _ in range(h)]
    visited[0][0] = 1
    q = deque([[0, 0]])
    while q:
        cy, cx = q.popleft()
        if cx == w-1 and cy == h-1:
            return True
        for i in range(4):
            ny, nx = cy + dy[i], cx + dx[i]
            if 0 <= ny < h and 0 <= nx < w:
                if not visited[ny][nx]:
                    visited[ny][nx] = 1
                    if board[ny][nx] == '0':
                        q.append([ny, nx])
                    else:
                        board[ny][nx] = '0'
                        count[ny][nx] = num
    return False


solution()