6087. 레이저 통신

업데이트 시간 : 2023-12-06 06:45:43 +0000

[Gold III] 레이저 통신 - 6087

문제 링크

성능 요약

메모리: 116376 KB, 시간: 196 ms

분류

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

제출 일자

2023년 12월 6일 15:45:33

문제 설명

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

💡 Solutions

📄 레이저 통신.py

from collections import deque
import sys

input = sys.stdin.readline
INF = int(1e9)

# 서-북-동-남
dx = [0, -1, 0, 1]
dy = [-1, 0, 1, 0]


def bfs(sx, sy, ex, ey):
    q = deque()
    visited = [[[INF] * 4 for _ in range(w)] for _ in range(h)] # ✅

    for i in range(4):
        nx = sx + dx[i]
        ny = sy + dy[i]
        if 0 <= nx < h and 0 <= ny < w and board[nx][ny] != "*":
            q.append((nx, ny, i))
            visited[nx][ny][i] = 0

    while q:
        x, y, direct = q.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < h and 0 <= ny < w and board[nx][ny] != "*":
                cnt = visited[x][y][direct]
                if direct == 0 or direct == 2:
                    if i == 1 or i == 3:
                        cnt += 1
                else:
                    if i == 0 or i == 2:
                        cnt += 1

                if visited[nx][ny][i] == -1:  # 방문한 적이 없음
                    visited[nx][ny][i] = cnt
                    q.append((nx, ny, i))
                else:  # 방문을 했는데 이전 거울개수보다 최솟값이라면
                    if visited[nx][ny][i] > cnt:
                        visited[nx][ny][i] = cnt
                        q.append((nx, ny, i))

    return min(visited[ex][ey])


if __name__ == "__main__":
    w, h = map(int, input().split())

    pos = []
    board = []
    for i in range(h):
        board.append(list(input().strip()))
        for j in range(w):
            if board[i][j] == "C":
                pos.append((i, j))

    print(bfs(pos[0][0], pos[0][1], pos[1][0], pos[1][1]))