흙금이네 블로그

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

알고리즘

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

흙금 2023. 4. 11. 20:20

 

 

아이디어

 

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()

 

'알고리즘' 카테고리의 다른 글

[BOJ] 1981 - 배열에서 이동 (Python)  (0) 2023.04.11
[BOJ] 1039 - 교환 (Python)  (0) 2023.04.11
[BOJ] 9376 - 탈옥 (Python)  (0) 2023.04.11
[BOJ] 2933 - 미네랄 (Python)  (0) 2023.04.11
[BOJ] 11401 - 이항 계수 3 (Python)  (0) 2023.04.10
Comments