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

접근

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

6087번: 레이저 통신

처음에는 BFS 알고리즘을 이용하여 visited 배열 (r, c) 에 해당 위치에 도달할 수 있는 최소 거울 수를 저장해가면서 탐색하면 아주 쉽게 풀 수 있을 것이라고 생각했다. 하지만 그 생각이 틀렸다는 것을 알 때까지는 오래 걸리지 않았고, 이후에는 꺾은 수가 적은 경우를 먼저 탐색하는 0 1 BFS 방법을 이용도 해봤지만 잘 되지 않았다.

결론적으로는 BFS 알고리즘을 변형하여 (r, c) 에서 상하좌우 4방향으로 끝에 막힐 때까지 쭉 탐색을 먼저 해주고, 이후 꺾일 때 visited 를 1 더해주는 식으로 탐색하여 문제를 해결하였다. 코드를 보면 더 쉽게 이해할 수 있다.

def bfs(sr, sc, er, ec):
    visited = [[-1] * C for _ in range(R)]
    queue = deque()
    visited[sr][sc] = 0
    queue.append((sr, sc))
    while queue:
        r, c = queue.popleft()
        for i in range(4):
            nr, nc = r + dr[i], c + dc[i]
            while 1:
                if (
                    # 배열 바깥으로 나가거나
                    nr < 0
                    or R <= nr
                    or nc < 0
                    or C <= nc
                    # 벽을 만나거나
                    or matrix[nr][nc] == "*"
                    # 다음 위치가 이미 방문되었는데, 현재 탐색중인 거울 수보다 작은 횟수로 이동 가능할 경우
                    or 0 < visited[nr][nc] < visited[r][c] + 1
                ):
                    # 해당 방향 탐색 종료
                    break
                # 위치를 큐에 추가하고
                queue.append((nr, nc))
                # visited[nr][nc] 를 visited[r][c] + 1 로 저장함으로써, (r, c)에서 출발하여 네 방향에 있는 모든 미방문 점은 같은 수를 가지게 된다.
                visited[nr][nc] = visited[r][c] + 1
                nr, nc = nr + dr[i], nc + dc[i]
    # 처음 시작 위치가 0으로 시작하여, 0회로 도달할 수 있는 곳을 1로 저장했기 때문에 마지막에 1을 뺀 값을 출력해준다.
    return visited[er][ec] - 1

코드

import sys
from collections import deque

input = sys.stdin.readline

dr = [0, 1, 0, -1]
dc = [1, 0, -1, 0]


def bfs(sr, sc, er, ec):
    visited = [[-1] * C for _ in range(R)]
    queue = deque()
    visited[sr][sc] = 0
    queue.append((sr, sc))
    while queue:
        r, c = queue.popleft()
        for i in range(4):
            nr, nc = r + dr[i], c + dc[i]
            while 1:
                if (
                    # 배열 바깥으로 나가거나
                    nr < 0
                    or R <= nr
                    or nc < 0
                    or C <= nc
                    # 벽을 만나거나
                    or matrix[nr][nc] == "*"
                    # 다음 위치가 이미 방문되었는데, 현재 탐색중인 거울 수보다 작은 횟수로 이동 가능할 경우
                    or 0 < visited[nr][nc] < visited[r][c] + 1
                ):
                    # 해당 방향 탐색 종료
                    break
                # 위치를 큐에 추가하고
                queue.append((nr, nc))
                # visited[nr][nc] 를 visited[r][c] + 1 로 저장함으로써, (r, c)에서 출발하여 네 방향에 있는 모든 미방문 점은 같은 수를 가지게 된다.
                visited[nr][nc] = visited[r][c] + 1
                nr, nc = nr + dr[i], nc + dc[i]
    # 처음 시작 위치가 0으로 시작하여, 0회로 도달할 수 있는 곳을 1로 저장했기 때문에 마지막에 1을 뺀 값을 출력해준다.
    return visited[er][ec] - 1


C, R = map(int, input().split())
matrix = [list(input().strip()) for _ in range(R)]
cs = []
for i in range(R):
    for j in range(C):
        if matrix[i][j] == "C":
            cs += [i, j]
            matrix[i][j] = "."
ans = bfs(cs[0], cs[1], cs[2], cs[3])
print(ans)

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!