2151. 거울 설치
업데이트 시간 : 2023-12-26 08:55:31 +0000[Gold III] 거울 설치 - 2151
성능 요약
메모리: 36248 KB, 시간: 92 ms
분류
너비 우선 탐색, 데이크스트라, 그래프 이론, 그래프 탐색, 최단 경로
제출 일자
2023년 12월 26일 17:55:23
문제 설명
채영이는 거울을 들여다보는 것을 참 좋아한다. 그래서 집 곳곳에 거울을 설치해두고 집 안을 돌아다닐 때마다 거울을 보곤 한다.
채영이는 새 해를 맞이하여 이사를 하게 되었는데, 거울을 좋아하는 그녀의 성격 때문에 새 집에도 거울을 매달만한 위치가 여러 곳 있다. 또한 채영이네 새 집에는 문이 두 개 있는데, 채영이는 거울을 잘 설치하여 장난을 치고 싶어졌다. 즉, 한 쪽 문에서 다른 쪽 문을 볼 수 있도록 거울을 설치하고 싶어졌다.
채영이네 집에 대한 정보가 주어졌을 때, 한 쪽 문에서 다른 쪽 문을 볼 수 있도록 하기 위해 설치해야 하는 거울의 최소 개수를 구하는 프로그램을 작성하시오.
거울을 설치할 때에는 45도 기울어진 대각선 방향으로 설치해야 한다. 또한 모든 거울은 양면 거울이기 때문에 양 쪽 모두에서 반사가 일어날 수 있다. 채영이는 거울을 매우 많이 가지고 있어서 거울이 부족한 경우는 없다고 하자.
거울을 어떻게 설치해도 한 쪽 문에서 다른 쪽 문을 볼 수 없는 경우는 주어지지 않는다.
입력
첫째 줄에 집의 크기 N (2 ≤ N ≤ 50)이 주어진다. 다음 N개의 줄에는 N개의 문자로 집에 대한 정보가 주어진다. ‘#’는 문이 설치된 곳으로 항상 두 곳이며, ‘.’은 아무 것도 없는 것으로 빛은 이 곳을 통과한다. ‘!’은 거울을 설치할 수 있는 위치를 나타내고, ‘*’은 빛이 통과할 수 없는 벽을 나타낸다.
출력
첫째 줄에 설치해야 할 거울의 최소 개수를 출력한다.
💡 Solutions
📄 거울 설치.py
import heapq
from collections import namedtuple
INF = float('inf')
Node = namedtuple('Node', ['x', 'y', 'd', 'cnt'])
dx = [0, 0, 1, -1] # x방향 설정
dy = [1, -1, 0, 0] # y방향 설정
def set_door_direction(door, dist, pq):
x, y = door[0].x, door[0].y
# 문 앞에서 이동할 수 있는 방향을 체크한 후 pq에 넣어서 이동을 시킬 수 있도록 작업한다.
for d in range(4):
nx, ny = x + dx[d], y + dy[d]
if 0 <= nx < n and 0 <= ny < n and grid[nx][ny] != '*':
heapq.heappush(pq, Node(x, y, d, 0))
dist[x][y][d] = 0
def dijkstra(door, dist, pq):
global ans
while pq:
x, y, d, cnt = heapq.heappop(pq)
if (x, y) == (door[1].x, door[1].y):
ans = min(cnt, ans)
# return cnt
nx, ny = x + dx[d], y + dy[d]
if 0 <= nx < n and 0 <= ny < n and grid[nx][ny] != '*':
if grid[nx][ny] == '!': # 경로에 거울을 설치할 수 있을 경우
nd = [0, 1] if d > 1 else [2, 3]
for i in nd:
if dist[nx][ny][i] > cnt + 1:
heapq.heappush(pq, Node(nx, ny, i, cnt + 1))
dist[nx][ny][i] = cnt + 1
if dist[nx][ny][d] > cnt: # 경로에 cnt 가 더 작을경우는 cnt로 변경한 뒤 pd에 투입
heapq.heappush(pq, Node(nx, ny, d, cnt))
dist[nx][ny][d] = cnt
return INF
n = int(input())
grid = [list(input().strip()) for _ in range(n)]
dist = [[[INF] * 4 for _ in range(n)] for _ in range(n)] # 각 방향에 대하여 이동이 가능한지 여부 파악하기
pq = [] # 힙큐
door = []# 시작과 끝 넣어둔 배열
ans = INF
for i in range(n):
for j in range(n):
if grid[i][j] == '#':
door.append(Node(i, j, -1, 0))
set_door_direction(door, dist, pq) # 초기 경로 매핑하기
dijkstra(door, dist, pq)
print(ans)