백준 2665 | 미로만들기 (BFS, 우선순위 큐)

문제 출처 : https://www.acmicpc.net/problem/2665

문제

• n x n 바둑판 모양의 n^2개의 방이 있다
• 방은 검은 방과 흰 방으로 구성되어 있다.
• 검은방은 사면이 벽으로 싸여 있어 들어갈 수 없다
• 서로 붙어 있는 두 개의 흰 방 사이에는 문이 있어서 지나다닐 수 있다.
• 왼줄 맨 왼쪽 방은 시작방으로서 항상 흰 방이고,
• 아랫줄 맨 오른쪽 방은 끝 방으로서 역시 흰 방이다
• 시작방에서 출발하여 끝방으로 가는것이 목적이다
• 시작방에서 끝 방으로 갈 수 없을때, 부득이 하게 검은 방 몇 개를 흰 방으로 바꾸어야한다.
• 되도록이면 적은 수의 방의 색을 바꾸고 싶다
  
  

문제 접근 방법

• 어쨌든 시작방에서 끝방으로 이동해야하는데 지나는 검은 방의 개수가 최소가 되고 싶다.
• 최대한 흰 방을 먼저 다 탐색하고, 흰 방만 거쳐서는 목적지에 갈 수 없다면 그 때 검은 방을 탐색한다.
  • 검은 방을 만나면 검은방보다 흰방을 먼저 탐색하기 위해서 우선순위 큐 (최소 힙)을 이용한다.
  • 흰 방 : 0, 검은 방 : +1 로 우선순위 큐에 저장하여 큐에 검은 방이 있더라도 흰 방을 우선적으로 탐색할 수 있게 한다.
• 검은 방을 지날 경우 우선순위 큐에 count 변수에 + 1 해서 흰 방보다 늦게 탐색되게 하고, 동시에 검은 방의 개수를 셀 수 있도록 한다.

BFS 알고리즘은 최단거리를 보장하는데
우선순위 큐(최소 힙)를 이용하여 흰 방을 우선적으로 탐색하기 때문에
검은 방을 최소한으로 거치면서 목적지에 도착할 수 있다.

코드

import sys
import heapq

input = sys.stdin.readline

n = int(input())
maze = []
for _ in range(n):
    maze.append(list(map(int, input().rstrip())))

# 2차원 리스트에서 상하좌우 이동을 위한 dirction x, direction y 변수 선언
dx = [1, -1 ,0, 0]
dy = [0, 0, 1, -1]

# 방문 여부 체크를 위한 visited 2차원 리스트
visited = [[False] * n for _ in range(n)]

def bfs(x, y):
    heap = []
    heapq.heappush(heap, (0, x, y))

    while heap:
        count, cx, cy = heapq.heappop(heap)
        visited[cx][cy] = True

        # 도착지점에 도착했을 경우
        if cx == (n - 1) and cy == (n - 1):
            return count

        # 상하좌우로 한칸씩 이동하여 탐색 진행
        for i in range(4):
            nx = cx + dx[i]
            ny = cy + dy[i]

            if (0 <= nx < n) and (0 <= ny < n) and not visited[nx][ny]:
                # 방문처리
                visited[nx][ny] = True
                # 흰 방
                if maze[nx][ny] == 1:
                    heapq.heappush(heap, (count, nx, ny))
                # 검은 방
                else:
                    heapq.heappush(heap, (count + 1, nx, ny))

print(bfs(0, 0))

다익스트라로 푸는 방법 참고해서 공부할 것

• https://2jinishappy.tistory.com/119