[BOJ] 6087 - 레이저 통신 (Python)

 

 

아이디어

 

BFS로 한 C칸에서 다른 C칸까지의 각 칸에 방문하기 위해 설치해야 할 최소 거울 개수를 구해 나간다.

 

 

풀이

 

import sys

input = sys.stdin.readline

delta = [(-1, 0), (0, 1), (1, 0), (0, -1)]

def solution():
    W, H = map(int, input().split())
    board = [[*input().rstrip()] for _ in range(H)]
    visited = [[-1]*W for _ in range(H)]
    K = max(W, H)
    points = []
    for r in range(H):
        for c in range(W):
            if board[r][c] == 'C':
                points.append((r, c))
    stack = [points[0]]
    visited[points[0][0]][points[0][1]] = 0
    cnt = 0
    while stack:
        _stack = []
        while stack:
            r, c = stack.pop()
            for dr, dc in delta:
                nr, nc = r+dr, c+dc
                for _ in range(K-1):
                    if H > nr >= 0 and W > nc >= 0 and board[nr][nc] != '*':
                        if visited[nr][nc] == -1:
                            visited[nr][nc] = cnt
                            _stack.append((nr, nc))
                            if nr == points[1][0] and nc == points[1][1]:
                                print(cnt)
                                return
                        elif visited[nr][nc] < cnt:
                            break
                    else:
                        break
                    nr += dr
                    nc += dc
        stack = _stack
        cnt += 1

solution()