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

난이도 : GOLD IV

문제링크 : https://www.acmicpc.net/problem/6087

문제해결 아이디어

• 마냥 최단거리 문제가 아닌 거울을 횟수를 최소화 하는 문제이므로
• 최단거리보다 더 많은 방문을 거치며 도착했음에도 거울개수가 더적은 경우가 있다.
• 이에 방문했던곳을 재방문할때 거울 사용횟수가 더 적은 경우에만 재방문 가능하게 했다.

소스코드

from collections import deque
import sys

input = sys.stdin.readline

m, n = map(int, input().split())

board = []

for _ in range(n):
    board.append(list(input().strip()))

# 원래는 최단경로가 아닌데 거울 때문에 최단경로가 되는 케이스?
# direction 방향 두개로 하고 bfs 돌리자
dx, dy = [1, 0, -1, 0], [0, 1, 0, -1]

target = []

for i in range(n):
    for j in range(m):
        if board[i][j] == 'C':
            target.append((i, j))

ans = int(1e9)


def bfs(x, y):
    global ans
    q = deque()
    visited = [[0] * m for _ in range(n)]
    visited[x][y] = 0
    q.append((x, y, -1, 0))

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

        if x == target[1][0] and y == target[1][1]:
            ans = min(ans, cnt)
            continue
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < m and board[nx][ny] != '*':
                if cnt == visited[x][y]:
                    if not visited[nx][ny]:
                        if d == -1 or d == i:
                            visited[nx][ny] = cnt
                            q.append((nx, ny, i, cnt))

                        elif d != i:
                            visited[nx][ny] = cnt + 1
                            q.append((nx, ny, i, cnt + 1))

                    else:
                        if d == i and visited[nx][ny] >= cnt:
                            q.append((nx, ny, i, cnt))
                            visited[nx][ny] = cnt
                        elif d != i and visited[nx][ny] >= cnt + 1:
                            q.append((nx, ny, i, cnt + 1))
                            visited[nx][ny] = cnt + 1


bfs(target[0][0], target[0][1])

print(ans)