🛸Problem
크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다.
'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 설치해야 하는 거울 개수의 최솟값을 구하는 프로그램을 작성하시오. 레이저로 통신한다는 것은 두 칸을 레이저로 연결할 수 있음을 의미한다.
레이저는 C에서만 발사할 수 있고, 빈 칸에 거울('/', '\')을 설치해서 방향을 90도 회전시킬 수 있다.
아래 그림은 H = 8, W = 7인 경우이고, 빈 칸은 '.', 벽은 '*'로 나타냈다. 왼쪽은 초기 상태, 오른쪽은 최소 개수의 거울을 사용해서 두 'C'를 연결한 것이다.
7 . . . . . . . 7 . . . . . . .
6 . . . . . . C 6 . . . . . /-C
5 . . . . . . * 5 . . . . . | *
4 * * * * * . * 4 * * * * * | *
3 . . . . * . . 3 . . . . * | .
2 . . . . * . . 2 . . . . * | .
1 . C . . * . . 1 . C . . * | .
0 . . . . . . . 0 . \-------/ .
0 1 2 3 4 5 6 0 1 2 3 4 5 6입력
첫째 줄에 W와 H가 주어진다. (1 ≤ W, H ≤ 100)
둘째 줄부터 H개의 줄에 지도가 주어진다. 지도의 각 문자가 의미하는 것은 다음과 같다.
.: 빈 칸
*: 벽
C: 레이저로 연결해야 하는 칸
'C'는 항상 두 개이고, 레이저로 연결할 수 있는 입력만 주어진다.
출력
첫째 줄에 C를 연결하기 위해 설치해야 하는 거울 개수의 최솟값을 출력한다.
Solution
문제를 보고 먼저 최단 거리를 찾은 다음, 방향이 바뀌는 순간을 계산해서 거울의 갯수를 구하면 되겠다고 생각했다. 하지만 레이저가 이동할 수 있는 방향이 4가지이다보니 최단 거리를 구하는게 생각보다 어려웠다. 첫 번째로 구한 방법은 일단 한 방향을 정해서 그 방향으로 나아가다 벽에 이동할 수 없는 경우에 다른 방향을 탐색하는 방법이다. 하지만 이 방법을 이용하면 중복해서 같은 곳을 계속 탐색하게 되므로 시간초과가 발생한다. 두 번째 방법은 3차원 배열에 4가지 방향에서 오는 경우 사용하는 거울의 최소 갯수를 각각 저장하는 것이다. 이렇게 4가지 경우의 수를 나눠서 저장하면 해당 경로를 여러 번 재방문할 필요가 없어진다.
Python Code
from sys import stdin
from heapq import heappush, heappop
def bfs(x, y):
q = []
for i in range(4):
heappush(q, (i, x, y, 0))
count[i][x][y] = 0
while q:
direct, x, y, mirror = heappop(q)
# print(count)
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if 0 <= nx < h and 0 <= ny < w and board[nx][ny] != "*":
new_mirror = mirror + 1 if direct != i else mirror
if count[i][nx][ny] > new_mirror:
count[i][nx][ny] = new_mirror
heappush(q, (i, nx, ny, new_mirror))
w, h = map(int, stdin.readline().split())
board = [stdin.readline().strip('\n') for _ in range(h)]
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
C_locate = []
for i in range(h):
for j in range(w):
if board[i][j] == "C":
C_locate.append((i, j))
(start_x, start_y), (end_x, end_y) = C_locate
count = [[[float('inf') for _ in range(w)] for _ in range(h)] for _ in range(4)]
bfs(start_x, start_y)
print(min(count[0][end_x][end_y], min(count[1][end_x][end_y], min(count[2][end_x][end_y], count[3][end_x][end_y]))))
