[6087] 레이저 통신 (BFS)

6087번: 레이저 통신

 

분석

1. 어떤 칸에서 이동할 수 있는 정점은 인접한 네 칸이 아닌 같은 방향 일직선
2. 한번에 이동할 수 있는 방향을 한번에 큐에 넣음
3. 이동 경로가 바뀌면 거울이 필요
4. 거울의 개수 = 직선의 개수 구한 뒤 -1 한 값
5. (sx,sy) 에서 (ex,ey)로 가는 최단거리를 구하는 문제

 

풀이

"""
W×H 크기의 지도
레이저는 C에서만 발사할 수 있고, 빈 칸에 거울('/', '\')을 설치해서 방향을 90도 회전시킬 수 있다.
빈 칸은 '.', 벽은 '*'로 나타냈다. 왼쪽은 초기 상태, 오른쪽은 최소 개수의 거울을 사용해서 두 'C'를 연결한 것이다.
C를 연결하기 위해 설치해야 하는 거울 개수의 최솟값을 출력
"""
from collections import deque
dx = [0,0,1,-1]
dy = [1,-1,0,0]
W,H=map(int, input().split())
a=[input() for _ in range(H)]
sx=sy=ex=ey=-1
for i in range(H):
    for j in range(W):
        if a[i][j] == 'C':
            if sx == -1:
                sx,sy = i,j
            else:
                ex,ey = i,j
dist = [[-1]*W for _ in range(H)]
q = deque()
dist[sx][sy] = 0
q.append((sx,sy))

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

    for k in range(4):
        nx,ny = x+dx[k],y+dy[k]
        # 한 방향으로 쭉 감
        while 0<=nx<H and 0 <=ny<W:
            if a[nx][ny] == '*':  # 벽
                break
            if dist[nx][ny] == -1:  # 방문하지 않았다면
                dist[nx][ny]=dist[x][y]+1  # 직선의 길이 +1
                q.append((nx,ny))
            nx += dx[k]
            ny += dy[k]

for i in range(H):
    for j in range(W):
        print(dist[i][j], end="  ")
    print()
print(dist[ex][ey]-1)