백준 6087 파이썬 - 레이저 통신

 

https://www.acmicpc.net/problem/6087

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

코드

import sys
from collections import deque
w, h = map(int, sys.stdin.readline().split())
board = [list(map(str, sys.stdin.readline().rstrip())) for _ in range(h)]
visited = [[1e9] * w for _ in range(h)]
dr = [[-1, 0], [1, 0], [0, 1], [0, -1]]
cArray = []
for i in range(h):
    for j in range(w):
        if board[i][j] == 'C':
            cArray.append((i, j))
(fx, fy), (sx, sy) = cArray
def bfs(x, y):
    queue = deque([(x, y)])
    visited[x][y] = 0
    while queue:
        x, y = queue.popleft()
        for dx, dy in dr:
            nx, ny = x + dx, y + dy
            while True:
                if not (0 <= nx < h and 0 <= ny < w):
                    break
                if board[nx][ny] == "*":
                    break
                if visited[nx][ny] < visited[x][y] + 1:
                    break
                queue.append((nx, ny))
                visited[nx][ny] = visited[x][y] + 1
                nx, ny = nx + dx, ny + dy
bfs(fx, fy)
sys.stdout.write(str(visited[sx][sy] - 1))

풀이

한 방향으로 계속 탐색하는 방식을 사용해야 편하다. while True 안에서 계속 한 방향으로 가는데 조건들에 맞으면  break를 한다. 첫 번째 C를 함수에 넣어 두번 째 C의 visited값을 활용해 출력한다.