[BOJ] 6087. 레이저 통신(Python) / BFS

www.acmicpc.net/problem/6087

6087번: 레이저 통신

 

연속으로 BFS 최단거리 문제를 풀었다.

문제를 처음 접했을 때 이전의 로봇 문제처럼 맵을 방향별로 만들어줘야겠다는 생각을 했는데, 

조금 더 생각해보니 그렇게까지 할 필요는 없을 것 같고, 머릿 속으로 BFS 이차원 맵을 어떻게 채울지 생각했다.

• 초기 check 맵을 최댓값 float('inf')으로 채워 놓는다.
• 시작 위치에서 4방향으로 쭉쭉 직진으로 벽이나 격자 밖으로 나갈 때까지 그려주고, 그 다음은 금방 그려준 위치들에서 4방향으로 쭉쭉 거울 사용 횟수 + 1한 값을 그려준다.
  • 이 때, 새 위치로 이동할 때 이동할 위치에 있는 거울이 현재까지 사용한 거울+1보다 작으면 갱신할 수 없다.
  • 즉, 최소 사용횟수(가장 처음 도달했을 때)일 때만 최댓값으로 이뤄진 맵의 해당 위치의 값을 갱신할 수 있다.
  • 최소 사용횟수가 아니라면 이미 방문처리 된 것. 더이상 가볼필요 없으므로 break로 while문 나간다.
• 목적지에 도달했을 때, check 맵에 그려진 최소 거울 사용 횟수를 즉시 리턴한다.

 

파이썬 코드는 다음과 같다.

---

from sys import stdin
input = stdin.readline
from collections import deque

dr = (-1, 1, 0, 0)
dc = (0, 0, -1, 1)

def bfs():
    check = [[float('inf')] * W for _ in range(H)]
    check[sr][sc] = -1
    Q = deque([(sr, sc)])
    while Q:
        r, c = Q.popleft()
        if (r, c) == (gr, gc):
            return check[gr][gc]

        # 4방향으로 각각 직진
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            while True:
                if not (0 <= nr < H and 0 <= nc < W):   # 격자 벗어나거나
                    break
                if A[nr][nc] == "*":                    # 벽 만나면 break
                    break
                if check[nr][nc] < check[r][c] + 1:     # 이동할 위치에 있는 거울이 현재까지 사용한 거울+1보다 작으면 갱신 X
                    break
                Q.append((nr, nc))                      # 새 위치 이동
                check[nr][nc] = check[r][c] + 1
                nr += dr[i]
                nc += dc[i]

# main
W, H = map(int, input().split())
A, C = [], []
sr, sc, gr, gc = 0, 0, 0, 0
for i in range(H):
    A.append(list(input().strip()))
    for j in range(W):
        if A[i][j] == "C":
            C.append((i, j))
(sr, sc), (gr, gc) = C
print(bfs())

---

• 시간 : 176ms / 126396KB
• 고찰 : 가끔씩 이렇게 BFS 맵을 최댓값으로 채워놓고 최솟값으로 갱신하는 문제들이 나온다. 이런 문제를 만났을 때, 해결 방법이 바로 떠오를 수 있도록 문제 많이 풀고 익숙해지자. 경험이 힘이다.