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

백준 6087 레이저 통신

다익스트라 알고리즘을 활용해야겠다고 생각했고, BFS 탐색을 통해 값을 구하려고 했다. 거리가 기준이 아닌 꺾인 횟수를 기준으로 다익스트라를 구현했고 몇 번의 시행착오 끝에 구현에 성공했다. 하지만, 다른 분의 Solution이 너무 우아해서 정리하려고 한다.

1. 현재 cnt에 해당하는 모든 케이스를 queue에 넣는다. (꺾이는 횟수를 저장하는 cnt 숫자에 해당하는 케이스는 queue에 들어간 상태다.)
2. 위치를 탐색하면 다음 cnt에 해당하는 위치는 next_queue에 저장하고 현재 queue가 비면 cnt를 1만큼 더하고 next_queue가 queue가 된다.
3. 이와 같은 방식이면 메모리는 효율적으로, cnt라는 변수를 q에 넣을 필요가 없어 굉장히 효율적이다.

import sys

input = sys.stdin.readline

delta = [(-1, 0), (0, 1), (1, 0), (0, -1)]

def solution():
    w, h = map(int, input().split())
    grid = [[*input().rstrip()] for _ in range(h)]
    dp = [[-1]*w for _ in range(h)]
    k = max(w, h)
    target = []
    for r in range(h):
        for c in range(w):
            if grid[r][c] == 'C':
                target.append((r, c))
    q = [target[0]]
    dp[target[0][0]][target[0][1]] = 0
    cnt = 0
    while q:
        next_q = []
        while q:
            r, c = q.pop()
            for dr, dc in delta:
                nr, nc = r+dr, c+dc
                for _ in range(k-1):
                    if h > nr >= 0 and w > nc >= 0 and grid[nr][nc] != '*':
                        if dp[nr][nc] == -1:
                            dp[nr][nc] = cnt
                            next_q.append((nr, nc))
                            if nr == target[1][0] and nc == target[1][1]:
                                print(cnt)
                                return
                        elif dp[nr][nc] < cnt:
                            break
                    else:
                        break
                    nr += dr
                    nc += dc
        q = next_q
        cnt += 1

solution()