[파이썬]백준 1261 알고스팟

링크

백준 1261 알고스팟

처음엔 흔한 bfs 문제인줄 알고 bfs로 접근했으나 코드를 적다보니 문제가 발생했다.
그냥 bfs로 풀면 방문했던 곳을 재방문 하면서 벽을 부순값을 다시 갱신해줘야 하는데 이부분을 처리하기가 까다로웠다.

어떻게 할 수 있을까 고민하다가 이문제는 벽을 최대한 피해서 가는 문제임을 깨달았다.
벽을 최대한 피하기 위해선 0인 곳을 먼저 방문하면 된다.
0인 곳을 먼저 방문하면 벽을 부수고 방문하는 것보다 반드시 벽을 부순 횟수가 작아진다.

따라서, bfs를 구현하되 0인 곳을 먼저 방문하도록 1일 경우엔 큐의 뒤쪽에, 0일 경우엔 큐의 앞쪽에 넣어주었다.

정답 코드

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

def bfs(r, c):
    breaking[r][c] = 0
    q = deque()
    q.append((r, c))
    while q:
        r, c = q.popleft()
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            if 0 <= nr < height and 0 <= nc < width:
                if breaking[nr][nc] == -1:
                    if maze[nr][nc] == '1':
                        breaking[nr][nc] = breaking[r][c] + 1
                        q.append((nr, nc))
                    if maze[nr][nc] == '0':
                        breaking[nr][nc] = breaking[r][c]
                        q.appendleft((nr, nc))

width, height = map(int, input().split())
maze = [input() for _ in range(height)]
breaking = [([-1] * width) for _ in range(height)]
dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]

bfs(0, 0)
print(breaking[height - 1][width - 1])

알게된 것👨‍💻

• bfs로 두가지 선택에서 더 나은 선택을 먼저하는 방법