[백준 2151] 거울 설치

 

2151번: 거울 설치

주어진 집에 대한 정보에서 '!'에 거울을 45도로 설치하여 '#'에서 다른 '#'으로 빛이 이동할 수 있도록 해야한다. 이때, 설치할 거울의 최소 개수를 계산하면 된다.

 

아래 코드는 좋은 코드가 아니다. 이 문제는 N의 제한이 50으로 작기 때문에 결론적으로 보면 큰 문제가 없는 솔루션이다.

내가 생각하는 좋은 풀이는 한칸씩 이동하면서 체크하는 방식이 아닌 거울을 설치해서 빛의 이동방향이 바뀌기 전까지 쭉 보면서 계산하는 방식으로 하는게 좋은 풀이라고 생각한다.

 

from collections import deque
import sys

def input():
    return sys.stdin.readline().rstrip()

def inrange(y, x, N):
    return 0 <= y and y < N and 0 <= x and x < N

Dy = (-1,0,1,0)
Dx = (0,-1,0,1)
N = int(input())
Map = [input() for i in range(N)]
dist = [[[-1 for j in range(N)] for i in range(N)] for k in range(4)]

start_point, end_point = (-1, -1), (-1, -1)

for i in range(N):
    for j in range(N):
        if Map[i][j] == '#':
            if start_point[0] == -1:
                start_point = (i, j)
            else:
                end_point = (i, j)

Q = deque()
for idx, (dy, dx) in enumerate(zip(Dy, Dx)):
    y, x = start_point
    ny, nx = y + dy, x + dx
    if inrange(ny, nx, N) and Map[ny][nx] != '*':
        Q.append((y, x, idx))
        dist[idx][y][x] = 0

while Q:
    y, x, d = Q.popleft()
    
    ny, nx = y + Dy[d], x + Dx[d]
    if inrange(ny, nx, N) and Map[ny][nx] != '*':
        if dist[d][ny][nx] == -1:
            dist[d][ny][nx] = dist[d][y][x]
            Q.append((ny, nx, d))
        else:
            if dist[d][ny][nx] > dist[d][y][x]:
                dist[d][ny][nx] = dist[d][y][x]
                Q.append((ny, nx, d))

    if Map[y][x] == '!':
        for k in [-1, 1]:
            idx = (d + k + 4) % 4
            ny, nx = y + Dy[idx], x + Dx[idx]
            if not inrange(ny, nx, N): continue
            if Map[ny][nx] == '*': continue
            if dist[idx][ny][nx] != -1: 
                if dist[idx][ny][nx] > dist[d][y][x] + 1:
                    dist[idx][ny][nx] = dist[d][y][x] + 1
                    Q.append((ny, nx, idx))
                continue
            dist[idx][ny][nx] = dist[d][y][x] + 1
            Q.append((ny, nx, idx))

ans = N * N
ey, ex = end_point
for k in range(4):
    if dist[k][ey][ex] == -1: continue
    if ans > dist[k][ey][ex]:
        ans = dist[k][ey][ex]

print(ans)