[백준] 6087번 - 레이저 통신 (파이썬)

https://www.acmicpc.net/problem/6087

# 레이저 통신
from collections import deque
import sys
input = sys.stdin.readline
MAX = sys.maxsize

M, N = map(int, input().split())
arr = []
C = []
for i in range(N):
    arr.append(list(input().strip()))
    for j in range(M):
        if arr[i][j] == 'C':
            C.append((i, j))
start, end = C[0], C[1]

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]


def bfs(a, b):
    global answer
    q = deque()
    q.append((a, b, -1, 0))
    visited = [[0] * M for _ in range(N)]
    visited[a][b] = 0
    while q:
        x, y, dir, result = q.popleft()
        # 도착지점 이라면 최소값 계산후 continue
        if (x, y) == end:
            answer = min(answer, result)
            continue
        for ndir in range(4):
            nx = x + dx[ndir]
            ny = y + dy[ndir]
            # 다음 위치가 범위 내이고, 벽이 아니라면
            if 0 <= nx < N and 0 <= ny < M and arr[nx][ny] != '*':
                # 현재 까지 사용한 거울의 수가 현 위치의 최소값과 같다면
                if result == visited[x][y]:
                    # 처음 방문 한다면
                    if not visited[nx][ny]:
                        if dir == -1 or dir == ndir:
                            visited[nx][ny] = result
                            q.append((nx, ny, ndir, result))
                        elif dir != ndir:
                            visited[nx][ny] = result + 1
                            q.append((nx, ny, ndir, result + 1))
                    # 이미 방문 했다면
                    else:
                        if dir == ndir and visited[nx][ny] >= result:
                            visited[nx][ny] = result
                            q.append((nx, ny, ndir, result))
                        elif dir != ndir and visited[nx][ny] >= result + 1:
                            visited[nx][ny] = result + 1
                            q.append((nx, ny, ndir, result + 1))


answer = MAX
bfs(start[0], start[1])
print(answer)

 

BFS
1. 입력을 받고 C의 위치 두 곳을 입력받는다. (C의 위치 한 곳은 시작 지점, 한 곳은 도착지점으로 설정)
2. visited는 거울을 사용한 최소 횟수를 저장한다.
3. BFS 실행
    - 현재 거울 방문 횟수가 visited의 횟수랑 다른 경우 최소값X 
    - 첫 방문
        - 첫출발 이거나 방향이 이전과 같다면 result 그대로 q에 append
        - 방향이 이전과 같다면 result + 1을 하여 q에 append
    - 첫 방문이 아니라면
        - 방향이 같고, 거울 사용횟수가 이동할 곳의 사용 횟수보다 작거나 같다면 result 그대로 append
        - 방향이 다르고, 거울 사용횟수 + 1이 이동할 곳의 사용 횟수보다 작거나 같다면 result + 1 append
    - 목표지점에 도착하면 최솟값 계산 이후, continue (빙돌아서 왔을 경우 거울 사용 횟수가 더 작을 수 있음)
4. answer 출력

 

최단 거리를 구하는 것이 아닌 거울 사용 횟수의 최솟값을 구하는 문제이다.

따라서 최단 거리보다 빙 돌아서 목표지점에 도착했을 때, 거울 사용횟수가 더 작을 수도 있다.

이에 방문했던 곳을 다시 방문할 수 있고, 거울의 사용횟수가 작은 값만 재방문할 수 있도록 설정했다.