문제 링크

미로 만들기

문제 설명

N*N크기의 보드 각각의 칸은 방으로 이루어져 있다. 까만 방은 사방이 막혀있어서 들어갈 수 없고, 두개의 하얀방 사이에는 문이 있어서 이동이 가능하다. 항상 하얀방인 (0,0)에서 (n-1,n-1)로 이동을 하려고 하는게 목적이다. 이동을 위해서 부득이 검은 방 몇 개를 흰 방으로 바꾸어야 하는데 되도록 적은 수의 방의 색을 바꾸고 싶다. 이때 최소 변경 횟수는?

문제 풀이

bfs인데 다익스트라를 활용해서 queue가 아닌 heap으로 구현하면 되는 문제이다. 매번 변경 횟수 count가 제일 짧은 것 부터 pop해서 계산하면 (n-1, n-1)에 도달했을때 최소 변경 횟수를 구할 수 있다.

import sys
import heapq

input = sys.stdin.readline
INF = int(1e9)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def in_range(x, y):
    if x in range(n) and y in range(n):
        return True
    return False

n = int(input())
board = []
for _ in range(n):
    board.append(list(map(int, input().strip())))
visited = [[False]*(n) for _ in range(n)]

queue = []
visited[0][0] = True
heapq.heappush(queue, (0,0,0))
while queue:
    count, x, y = heapq.heappop(queue)
    if x == n-1 and y == n-1:
        print(count)
        break
    
    for i in range(4):
        nx, ny = x+dx[i], y+dy[i]
        if in_range(nx, ny) and visited[nx][ny] == False:
            visited[nx][ny] = True
            if board[nx][ny] == 0:
                heapq.heappush(queue, (count+1, nx, ny))
            else:
                heapq.heappush(queue, (count, nx, ny))

bfs를 이렇게 접근해서 푸는 방법도 있구나,,, 약간만 바꾸면 되는데 생각해내는게 어려웠다. 하지만 한번 해봤으니 다음에 풀면 풀 수 있을 것 같군 ^ㄹ^