[레이저 통신/G3/Python3]

6087번 레이저 통신 G3

 

문제
크기가 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를 연결하기 위해 설치해야 하는 거울 개수의 최솟값을 출력한다.

 

 

그래프 이론, 그래프 탐색, 너비 우선 탐색, 최단 경로, 데이크스트라

 

 

데이크스트라 알고리즘을 사용하여 문제를 풀이했다.

거울 설치 횟수를 기준으로 우선 순위 큐를 사용하였다.

 

초기 레이저는 어느 방향으로 이동할 수 있으므로 4방향 모두 추가했다.

우선 순위 큐에서 꺼낸 값에서 갈 수 있는 모든 방향으로 레이저를 보냈다.

 

 

 

import sys
import heapq

row, col = map(int, sys.stdin.readline().split())
maps = [list(sys.stdin.readline().rstrip()) for _ in range(col)]

c_pos = [0, 0]

for y in range(col):
    for x in range(row):
        if maps[y][x] == "C": c_pos = [y, x]

move_list = [[0,1],[0,-1],[-1,0],[1,0]]

visit = [[[False] * row for _ in range(col)] for __ in range(4)]
hq = []
for i in range(4):
    heapq.heappush(hq, [0, c_pos, i])
maps[c_pos[0]][c_pos[1]] = "."

while hq:
    cnt, pos, index = heapq.heappop(hq)
    y, x = pos
    if visit[index][y][x]: continue
    visit[index][y][x] = True
    if maps[y][x] == "C":
        print(cnt)
        break

    for i in range(4):
        ay, ax = move_list[i]
        dy, dx = y+ay, x+ax
        if dy<0 or dx<0 or dy>=col or dx>=row: continue
        if visit[i][dy][dx] or maps[dy][dx] == "*": continue
        heapq.heappush(hq, [cnt + (1 if i != index else 0), [dy, dx], i])

 

---