백준: 6087 레이저 통신

문제

6087번: 레이저 통신

 

문제 풀이

 레이저와 레이저 사이의 통신을 하기 위해 최소한의 거울을 설치하여 통신이 가능하도록 하는 거울의 개수를 반환하는 문제이다. 문제를 풀기 위해서는 레이저가 방향을 바꾸지 않고 최대한 나아갈 수 있는 경우와, 방향을 바꾸는 경우를 생각하여 문제를 접근하면 다음과 같은 로직을 생각할 수 있다.

 

• BFS로 탐색을 시작한다.
• 방향을 바꾸지 않고 갈 수 있는 경로들을 최대한 탐색한다.
  • 범위를 벗어나지 않거나, 벽이 아닌 경우를 말한다.
• 방향이 바뀌게 된다면 기존에 방향을 바꾸지 않고 최대한 갈 수 있는 경우에서 +1 한다.
  • 즉, 방향이 변경되어 `거울 하나를 설치`하게 된다.
• 다른 레이저에 도달할 때 가지, 위의 로직을 반복하면 `최소 거울의 개수`를 찾을 수 있다.

 

코드

from sys import stdin
from collections import deque
from math import inf


def visitable(x, y):
    return 0 <= x < h and 0 <= y < w


def bfs():
    q = deque([start])
    visited[start[X]][start[Y]] = 0

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

        for dx, dy in dirs:
            next_x, next_y = x + dx, y + dy

            while visitable(next_x, next_y) and graph[next_x][next_y] != '*':
                if visited[next_x][next_y] < visited[x][y] + 1:
                    break

                q.append((next_x, next_y))
                visited[next_x][next_y] = visited[x][y] + 1

                next_x += dx
                next_y += dy

    return visited[end[X]][end[Y]] - 1


if __name__ == "__main__":
    X, Y = 0, 1
    dirs = ((0, 1), (0, -1), (1, 0), (-1, 0))
    w, h = map(int, stdin.readline().split())
    graph = [list(stdin.readline().rstrip()) for _ in range(h)]
    visited = [[inf] * w for _ in range(h)]
    laser = []

    for i in range(h):
        for j in range(w):
            if graph[i][j] == 'C':
                laser.append([i, j])

    start, end = laser
    print(bfs())