[백준] 6087번 레이저 통신 - Python / 알고리즘 중급 1/3 - BFS (연습)

ByungJik_Oh·2025년 5월 24일

Baekjoon Online Judge

[Baekjoon Online Judge]

목록 보기

151/244

💡 문제

크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다.

'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 설치해야 하는 거울 개수의 최솟값을 구하는 프로그램을 작성하시오. 레이저로 통신한다는 것은 두 칸을 레이저로 연결할 수 있음을 의미한다.

레이저는 C에서만 발사할 수 있고, 빈 칸에 거울('/', '\')을 설치해서 방향을 90도 회전시킬 수 있다.

아래 그림은 H = 8, W = 7인 경우이고, 빈 칸은 '.', 벽은 '*'로 나타냈다. 왼쪽은 초기 상태, 오른쪽은 최소 개수의 거울을 사용해서 두 'C'를 연결한 것이다.

입력

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

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

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

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

출력

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

💭 접근

이때까지 풀었던 BFS 문제 중 가장 어려웠던 문제였다.

이 문제를 해결하기 위해서 기본적으로 다익스트라 알고리즘을 사용하며,
이때까지 설치한 거울의 개수를 저장하고 이 거울의 개수를 바탕으로 다익스트라 알고리즘에 사용한다. 또한, 방문처리의 경우 주어진 지도 기준으로 가로, 세로 방향을 따로 체크하며, 여기서 상하좌우 4 방향을 고려하는 것이 아닌 2개의 방향으로 체크하는 것이 핵심이다.
(가는 방향이 중요한 것이 아닌, 두 지점('C')을 마치 파이프로 잇는다고 생각하면 된다.)

📒 코드

import sys
import heapq
input = sys.stdin.readline

def dijkstra(cnt, x, y):
    for i in range(4): # 우선 4방향으로 탐색 시작
        tmp_x = x
        tmp_y = y
        while True: # 갈 수 있는 끝까지 나아감
            nx = tmp_x + dx[i]
            ny = tmp_y + dy[i]

            if 0 <= nx < h and 0 <= ny < w:
                if graph[nx][ny] == '.': # 비어있는 공간
                    if can(nx, ny, cnt, i): # 거울 개수 or 방문 여부 확인
                        mirror[nx][ny] = cnt # 거울 개수 갱신
                        visited[i % 2][nx][ny] = 1 # 방문 처리
                        heapq.heappush(q, (cnt, nx, ny))
                        tmp_x = nx
                        tmp_y = ny
                    else:
                        break
                elif graph[nx][ny] == '*': # 벽이라면 break
                    break
                elif graph[nx][ny] == 'C': # 도착하면 정답 출력
                    print(cnt)
                    sys.exit()
            else:
                break

def can(nx, ny, cnt, direction): # 거울 개수 or 방문 여부 확인하는 함수
    # 이때까지 설치한 거울의 갯수보다 작거나
    # 갯수는 같은데 새로운 방향으로 나아간다면 True
    if mirror[nx][ny] > cnt or \
    (mirror[nx][ny] == cnt and visited[direction % 2][nx][ny] == 0):
        return True
    return False

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

# 현재까지 설치한 거울의 개수
mirror = [[sys.maxsize for _ in range(w)] for _ in range(h)]

# 방문여부 확인([0]은 세로 방향, [1]은 가로 방향)
# 왜 4방향이 아닌가? 두 지점이 이어지기만 하면 되기 때문에 하나의 파이프를 놓는다고 가정
visited = [[[0 for _ in range(w)] for _ in range(h)] for _ in range(2)]

# 아래, 오른쪽, 위, 왼쪽 순서
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

q = []
for i in range(h):
    for j in range(w):
        if graph[i][j] == 'C': # 어떤 한 C에서 시작
            heapq.heappush(q, (-1, i, j))
            graph[i][j] = '*' # 동일한 지점으로 돌아오지 않도록 벽으로 변경

            # 한번 반복될 때 마다 거울 설치
            # 한 방향으로 갈 수 있는 끝까지 진행되고 반복문이 돌아오기 때문에
            # 같은 방향으론 이미 방문처리가 되었으므로 반드시 거울이 설치됨
            while q:
                cnt, x, y = heapq.heappop(q)
                dijkstra(cnt + 1, x, y)