[파이썬] [BFS] 백준 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

입력

첫째 줄에 W와 H가 주어진다. (1 ≤ W, H ≤ 100)

둘째 줄부터 H개의 줄에 지도가 주어진다. 지도의 각 문자가 의미하는 것은 다음과 같다.

• .: 빈 칸
• *: 벽
• C: 레이저로 연결해야 하는 칸

'C'는 항상 두 개이고, 레이저로 연결할 수 있는 입력만 주어진다.

출력

첫째 줄에 C를 연결하기 위해 설치해야 하는 거울 개수의 최솟값을 출력한다.

예제 입력 1

7 8
.......
......C
......*
*****.*
....*..
....*..
.C..*..
.......

예제 출력 1

3

코드

import sys
from collections import deque
input=sys.stdin.readline
INF=sys.maxsize

dx=[-1,1,0,0]
dy=[0,0,-1,1]

def bfs():
    queue=deque()
    queue.append((sw,sh))
    visited[sw][sh]=-1
    while queue:
        x,y=queue.popleft()
        if (x,y)==(ew,eh):
            return visited[ew][eh]

        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            while 1:
                if not (0<=nx<h and 0<=ny<w): break
                if array[nx][ny]=='*': break
                if visited[nx][ny]<visited[x][y]+1: break
                visited[nx][ny]=visited[x][y]+1
                queue.append((nx,ny))
                nx+=dx[i]
                ny+=dy[i]

w,h=map(int, input().split())
array=[list(input().rstrip()) for _ in range(h)]

c=[]
for i in range(h):
    for j in range(w):
        if array[i][j]=='C':
            c.append([i,j])
sw,sh=c[0]
ew,eh=c[1]

visited=[[INF]*w for _ in range(h)]

print(bfs())

생각 정리

• 새 위치로 이동할 때 이동할 위치에 있는 거울이 현재까지 사용한 거울+1보다 작으면 갱신할 수 없다.
• 즉, 최소 사용횟수(가장 처음 도달했을 때)일 때만 최댓값으로 이뤄진 맵의 해당 위치의 값을 갱신할 수 있다.
• 최소 사용횟수가 아니라면 이미 방문처리 된 것. 더이상 가볼필요 없으므로 break로 while문 나간다.