6087: 레이저 통신

풀이 시간

• 55m
• 거울 개수를 최소로하는 루트를 찾기 위해 한 방향으로 갈 수 있을 때까지 가는 아이디어를 참고함

구현 방식

• 노드에 cnt (탐색하면서 사용한 거울 개수)를 추가해줌
• bfs를 탐색할 때, 최단거리 루트 + 거울 개수를 최소로하는 루트를 찾아야함
  -> nx, ny를 구하고 다음 노드로 갈 때, while문을 돌면서 해당 방향으로 최대한 가야함
  -> 범위를 벗어나거나, 벽을 만났을 경우 break 해주고, 아직 방문하지 않은 노드인 경우 (해당 방향으로 더 갈 수 있는 경우) queue에 append 해줌

코드

import sys
from collections import deque

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

def bfs(x, y):
    queue = deque([])
    queue.append([x, y, -1])
    visit[x][y] = True

    while queue:
        x, y, cnt = queue.popleft()

        if x == dest[0] and y == dest[1]:
            return cnt
        
        for i in range(4):
            nx = x; ny = y
            while True: #해당 방향으로 최대한 감
                nx += dx[i]; ny += dy[i]
                if nx < 0 or nx >= H or ny < 0 or ny >= W:
                    break
                if board[nx][ny] == '*':
                    break
                if not visit[nx][ny]: #해당 방향으로 더 갈 수 있는 경우
                    queue.append([nx, ny, cnt+1])
                    visit[nx][ny] = True
            


W, H = map(int, sys.stdin.readline()[:-1].split())
board = []; src_dest = []
for h in range(H):
    tmp = list(sys.stdin.readline()[:-1])
    for w in range(W):
        if tmp[w] == 'C':
            src_dest.append([h, w])
    board.append(tmp)
src, dest = src_dest

visit = [[False] * W for _ in range(H)]
print(bfs(src[0], src[1]))

결과