6087. 레이저 통신 (Python)

6087번: 레이저 통신

 

풀이

 BFS를 통해서 C에서 C로 갈 때 필요한 거울 개수의 최솟값을 구할 수 있다. BFS를 위한 큐에는 (행, 열, 이전에 이동했던 방향, 사용한 거울의 개수)와 같은 튜플의 형태로 값을 넣어줬다. 이전에 이동했던 방향을 넣어준 이유는 기존에 이동했던 방향 그대로 이동할 때는 거울을 사용하지 않고 이동하고 90도 방향으로 이동할 때는 거울을 사용하기 때문에 이를 체크하기 위해 사용했다. 반대 방향으로 이동하는 경우는 체크하지 않고 넘어간다(예를 들어 오른쪽으로 이동했을 경우에는 180도 꺾어서 왼쪽으로 이동하는 경우는 체크하지 않는다).

 

 BFS를 할 때, 보통 visited 배열로 해당 위치의 방문 체크를 하는데 이 문제의 경우는 단순히 방문 여부만을 체크하지 않고 해당 위치까지 오는데 사용한 최소 거울의 개수를 기록해둔다. 어떤 위치에 거울 2개를 사용하여 도착했다고 생각해보자. 하지만 이전에 해당 위치에 거울 1개를 사용하여 도착했다고 하면 현재 이동 정보는 계속 기록할 필요가 없다. 이처럼 거울을 더 많이 사용하여 도착하는 경우를 사전에 제거하기 위하여 visited를 사용한 거울의 개수를 사용하여 체크한다. 

 만약 어떤 위치에 같은 거울의 개수를 사용하여 도착했을 경우에는 탐색을 계속 진행해야 한다. 이유는 지금까지는 같은 거울의 개수를 사용했더라도 이후에 어떻게 진행하느냐에 따라서 다음 위치에 더 적은 개수의 거울을 사용하여 도착하는 경우가 있을 수 있기 때문이다.

 

 위와 같이 BFS 탐색을 하면 C에서 다른 C까지 사용하는 거울 개수의 최솟값을 구할 수 있다.

 

코드

# 범위 체크 함수
def isRange(x, y):
    return 0 <= x < H and 0 <= y < W


if __name__ == '__main__':
    W, H = map(int, input().split())
    board = []
    CPosition = []  # C 위치를 담아두는 리스트
    dir = [(-1, 0), (0, 1), (1, 0), (0, -1)]  # 이동 방향
    minMirror = float('inf')  # C에서 C로 가는데 사용한 거울 개수의 최솟값

    for i in range(H):
        tmp = input()
        board.append(tmp)

        for j in range(W):
            if len(CPosition) == 2:  # C 위치를 두 개 다 찾았으면 탐색하지 않음
                break

            if tmp[j] == 'C':  # C 위치를 찾았으면 담아준다.
                CPosition.append((i, j))

    # (행, 열, 이동한 방향, 사용한 거울의 개수)
    # 처음 이동 방향은 임의의 값으로 설정하여 4방향을 다 탐색하도록 해준다.
    q = [(CPosition[0][0], CPosition[0][1], -100, 0)]
    # visited[x][y] : board[x][y]에 도착했을 때 사용한 거울 개수의 최솟값
    visited = [[minMirror for _ in range(W)] for _ in range(H)]

    while q:
        x, y, direction, mirrorCount = q.pop(0)

        # 목표 C 방향에 도착하면 minMirror 갱신하고 다음 탐색으로
        if x == CPosition[1][0] and y == CPosition[1][1]:
            minMirror = min(minMirror, mirrorCount)
            continue

        for i in range(4):
            if abs(i - direction) == 2:  # 180도 방향(반대 방향)은 체크하지 않는다.
                continue

            nx = x + dir[i][0]
            ny = y + dir[i][1]

            # 범위를 벗어났거나 벽을 만나면 continue
            if not isRange(nx, ny) or board[nx][ny] == '*':
                continue

            # 현재 사용한 거울이 C에서 C로 갈 때 사용한 거울 개수의 최솟값보다 클 경우에는 탐색을 진행하지 않는다.
            if mirrorCount > minMirror:
                continue

            if direction == i:  # 전에 이동하던 방향과 같을 경우에는 거울을 사용하지 않는다.
                if visited[nx][ny] < mirrorCount:  # 더 많은 거울을 사용하여 board[nx][ny]에 도착했을 경우는 기록 x
                    continue
                visited[nx][ny] = mirrorCount
                q.append((nx, ny, i, mirrorCount))
            else:  # 전에 이동하던 방향에서 90도 회전시킨 방향일 경우 거울을 추가로 사용한다.
                # 더 많은 거울을 사용하여 board[nx][ny]에 도착했을 경우는 기록 x
                if visited[nx][ny] < mirrorCount + 1:
                    continue
                visited[nx][ny] = mirrorCount + 1
                q.append((nx, ny, i, mirrorCount + 1))

    print(minMirror - 1)  # 처음 4방향을 탐색할 때 거울을 하나 더 사용했으므로 마지막에 1을 빼준 값을 출력한다.