[백준(파이썬/Python)] 1261_알고스팟

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

1261번: 알고스팟

 

 

BFS와 우선순위큐(heapq)를 동시에 활용해서 푸는 문제입니다.

 

현재까지 부순 벽의 수를 count라는 변수에 저장하고, 상하좌우로 이동을 하며 벽이면 count+1, 벽이 아니면 count값을 그대로 우선순위 큐에 넣어주면 됩니다.

 

일반적인 bfs와는 다르게 우선순위 큐를 이용해야 하는 이유는 벽을 깨는 횟수를 "최소한"으로 하기 위해서인데, 다음 방문할 곳 중에서 벽이 없는 경우를 우선순위에 둠으로써 벽이 없는 경우를 제일 먼저 고려해주도록 해야 합니다.

 

이와 거의 동일한 문제가 백준2665번(미로 만들기)인데, 해당 문제에 대한 풀이도 아래에 있습니다.

https://studyandwrite.tistory.com/380

[백준(파이썬/Python)] 2665_미로만들기 - BFS, 우선순위 큐

[풀이]

import heapq
import sys

def bfs(x,y):
    visited = [[False] * m for _ in range(n)]

    q = []
    heapq.heappush(q,(0,x,y))
    visited[x][y] = True

    while q:
        count, curr_x, curr_y = heapq.heappop(q)
        if curr_x == n-1 and curr_y == m-1:
            return count
        for i in range(4):
            next_x, next_y = curr_x + dx[i], curr_y + dy[i]
            if 0 <= next_x < n and 0 <= next_y < m and not visited[next_x][next_y]:
                visited[next_x][next_y] = True

                # 벽으로 막혀있는 경우                
                if graph[next_x][next_y] == 1:
                    heapq.heappush(q,(count+1, next_x, next_y))
                # 벽이 없을 때
                else:                    
                    heapq.heappush(q,(count, next_x, next_y))

m, n = map(int, input().split())
graph = [list(map(int, list(sys.stdin.readline().rstrip()))) for _ in range(n)]
dx, dy = [1, 0, -1, 0], [0,1,0,-1]
print(bfs(0,0))