[백준] 6087_레이저 통신 :: Python

문제

🔗 [백준] 6087_레이저 통신

크기가 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

---

아이디어

• 레이저는 한 방향으로 쭉 나아간다.
• 거울은 레이저의 방향을 전환시키는 역할을 한다.
• 거울의 개수는 두 지점 C를 연결하는 데 필요한 직선의 개수 - 1이다.

---

풀이

import sys
input = sys.stdin.readline

from collections import deque

m, n = map(int, input().split())
arr = [list(input().strip()) for _ in range(n)]

# 시작점
start_loc = (0, 0)
# 종료지점
end_loc = (0, 0)

first = True
for r in range(n):
    for c in range(m):
        if arr[r][c] == 'C':
            if first:
                first = False
                start_loc = (r, c)
            else:
                end_loc = (r, c)
                break

dr = [0, 0, -1, 1]
dc = [-1, 1, 0, 0]

# mirrors[r][c] = (r, c) 위치까지 오는 데 필요한 거울의 최소 개수
mirrors = [[-1] * m for _ in range(n)]
q = deque([(start_loc[0], start_loc[1], 0)])
mirrors[start_loc[0]][start_loc[1]] = 0
while q:
    r, c, mirror = q.popleft()
    for i in range(4):
        nr = r
        nc = c 
        while 0 <= nr + dr[i] < n and 0 <= nc + dc[i] < m:
            nr += dr[i]
            nc += dc[i]
            if arr[nr][nc] == '*':
                break
            if mirrors[nr][nc] > -1 and mirrors[nr][nc] <= mirror + 1:
                continue
            mirrors[nr][nc] = mirror + 1
            q.append((nr, nc, mirror + 1))

answer = mirrors[end_loc[0]][end_loc[1]] - 1
print(answer)