99클럽 코테 스터디 15일차 (BOJ 2665 미로만들기)

오늘의 문제: BOJ 2665(미로만들기)

문제 설명

n×n 바둑판 모양으로 총 n2개의 방이 있다. 일부분은 검은 방이고 나머지는 모두 흰 방이다. 검은 방은 사면이 벽으로 싸여 있어 들어갈 수 없다. 서로 붙어 있는 두 개의 흰 방 사이에는 문이 있어서 지나다닐 수 있다. 윗줄 맨 왼쪽 방은 시작방으로서 항상 흰 방이고, 아랫줄 맨 오른쪽 방은 끝방으로서 역시 흰 방이다.

시작방에서 출발하여 길을 찾아서 끝방으로 가는 것이 목적인데, 아래 그림의 경우에는 시작방에서 끝 방으로 갈 수가 없다. 부득이 검은 방 몇 개를 흰 방으로 바꾸어야 하는데 되도록 적은 수의 방의 색을 바꾸고 싶다.

 

알고리즘

간단한 경로찾기 유형의 BFS 문제로 보일수 있으나 시작점(0,0) 부터 탈출지점(n-1,n-1)까지 최소한의 벽을 부셔서 가야하는 다익스트라 문제이다. 흰 방일 경우에는 코스트가 들지 않고 검은 방일 경우 코스트에 1을 추가하면서 각 지점을 통과하는데 최소한의 코스트를 구하면 된다.

 

from heapq import heappop, heappush

n = int(input())

dy = [0, 1, 0, -1]
dx = [1, 0, -1, 0]

matrix = [list(map(int, input().strip())) for _ in range(n)]
INF = float('inf')
check = [[INF for _ in range(n)] for _ in range(n)]


heap = []
check[0][0] = 0
heappush(heap, (0, 0, 0))

while heap:

    cost, y, x = heappop(heap)

    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]

        if 0 <= ny < n and 0 <= nx < n:
            if matrix[ny][nx] == 1:
                n_cost = cost
            else:
                n_cost = cost + 1

            if check[ny][nx] > n_cost:
                check[ny][nx] = n_cost
                heappush(heap, (n_cost, ny, nx))

print(check[n-1][n-1])