[백준] 거울 설치

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

2151번: 거울 설치

BFS와 우선순위 큐를 사용하여 해결하였습니다. 현재가 거울인 경우에는 기존 진행하던 방향에서 시계방향, 반시계 방향으로 90도 꺾어서 진행할 수 있습니다. 따라서, 현재가 그냥 빈 공간인지 아니면 거울을 놓을 수 있는지에 따라 다르게 진행해주면 됩니다. 여기서 주의해야할 점은 거리가 최단이 아닌 거울의 수를 최소로 해야한다는 점입니다. 거리가 최소이면 단순 큐를 사용해서 목표 지점에 먼저 도달한 순간 출력해주어야 하지만 이 문제의 경우에는 거울의 수가 최소여야하므로 거울을 최소로 설치했을 때가 먼저 큐에서 나와야하므로 우선순위 큐가 필요로 합니다.

 

import sys, heapq
from collections import deque
sys.stdin = open("input.txt", "r")
input = sys.stdin.readline
INT_MAX = sys.maxsize
n = int(input())

board = [
    list(input().rstrip())
    for _ in range(n)
]

startY, startX = -1, -1

for i in range(n):
    for j in range(n):
        if board[i][j] == '#':
            startY = i
            startX = j
            board[i][j] = '*'
            break
    if startY != -1:
        break

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

q = []

# visited[k][i][j]: k 방향으로 i, j에 도달한적이 있는지 체크한다.
visited = [
    [[INT_MAX] * n
    for _ in range(n)]
    for __ in range(4)
]

def inRange(y, x):
    return 0 <= y < n and 0 <= x < n

def getNextDir(dir):
    if dir == 0:
        return [1, 3]

    if dir == 1:
        return [0, 2]

    if dir == 2:
        return [1, 3]

    if dir == 3:
        return [0, 2]

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

    if inRange(ny, nx) and board[ny][nx] != '*':
        heapq.heappush(q, (0, ny, nx, i))
        visited[i][ny][nx] = 0

while q:
    cnt, y, x, dir  = heapq.heappop(q)
    # 다른 문에 도착한 경우에는 문의 개수를 체크해준다.
    if board[y][x] == '#':
        #print(y, x)
        print(cnt)
        break

    # 현재가 빈 공간이거나 거울을 사용할 수 있는 경우
    # 기존에 진행하던 방향으로 진행한다.
    if board[y][x] == '.' or board[y][x] == '!':
        ny = y + dy[dir]
        nx = x + dx[dir]

        if inRange(ny, nx) and board[ny][nx] != '*' and visited[dir][ny][nx] > cnt:
            visited[dir][ny][nx] = cnt
            heapq.heappush(q, (cnt, ny, nx, dir))

    # 거울을 사용하는 경우
    if board[y][x] == '!':
        nextDirs = getNextDir(dir)

        for i in nextDirs:
            ny = y + dy[i]
            nx = x + dx[i]

            if inRange(ny, nx) and board[ny][nx] != '*' and visited[i][ny][nx] > cnt + 1:
                visited[i][ny][nx] = cnt + 1
                heapq.heappush(q, (cnt + 1, ny, nx, i))