[백준 - Python] 6087 - 레이저 통신

0. 문제 링크

 

 

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

6087번: 레이저 통신

---

1. 풀이 방법

 

 

+ 23.02.04에서 문제를 다시 채점하니 시간 초과가 났습니다.ㅜ 

 

이 문제를 보고 맨 처음 떠오른 생각은 다익스트라였다.

최단 거리를 먼저 찾고, 최단 루트에서 방향이 바뀌는 부분이 거울이니까 그만큼 하면 되겠지 라는 생각을 했다.

하지만 이런 생각은 틀린게, 최단 루트가 최소 거울 개수를 보장하지 않는다!

아래 예시를 보자..

반례

중간으로 가는 루트가 가장 빠른 루트인데, 거울은 직진으로 쭉 가는 것보다 많이 쓴다.

따라서 다른 방법을 생각해야한다.

 

두 번째로 생각한 방법은 어떤 경로를 찾으면 우선 직진으로 쭉 가보는 것이다.

쭉 가면서 사용한 거울의 개수를 check 변수에 집어넣는다.

만약 동일한 곳(y, x)을 또 방문할 경우 내가 지금 사용한 거울의 개수가 기존의 check(y, x)에 저장된 값보다 작다면 그것 또한 탐색하는 방식으로 진행했다.

여기서 중요한 점이 있는데, 직진의 출발점 (y, x)는 그대로 놔두고, ny, nx만 바꾸는 것이다.

check[ny][nx]는 check[y][x] + 1이므로, 따로 사용된 거울의 개수를 저장할 필요가 없다.

만약 쭉 직진하다가 벽을 만날 경우 자동적으로 while 문이 종료되고, 다시 BFS를 진행하니 상관이 없다.

---

2. 코드

 

 

from collections import deque

w, h = map(int, input().split())
board = [[b for b in input()] for _ in range(h)]
root = [[99999 for _ in range(w)] for _ in range(h)]

check = []
for i in range(h):
    for j in range(w):
        if board[i][j] == 'C':
            check.append([i, j])
board[check[0][0]][check[0][1]] = 'C1'

root[check[0][0]][check[0][1]] = -1     # -1로 해야 특정 루트로 갔을 때 사용한 거울의 개수를 파악할 수 있음

dy, dx = [-1, 0, 1, 0], [0, 1, 0, -1]       # 위에서 시계 방향
dq = deque()
dq.append([*check[0]])

while dq:
    y, x = dq.popleft()
    for i in range(4):
        ny, nx = y + dy[i], x + dx[i]
        while True:     # 기존 방향으로 쭉 나아가기 위해
            if not (0 <= ny < h and 0 <= nx < w): break     # 만약 범위를 벗어난다면
            if board[ny][nx] == '*': break      # 벽을 만난다면
            if root[ny][nx] < root[y][x] + 1: break     # 이미 방문한 곳보다 더 많은 거울을 사용해야 하는 경우, 혹은 재방문을 하는 경우
            dq.append([ny, nx])
            root[ny][nx] = root[y][x] + 1       # 맨 처음 출발했던 위치에서 +1을 해야함
            ny += dy[i]     # 기존 방향으로 계속 나아감
            nx += dx[i]
print(root[check[1][0]][check[1][1]])

---

3. 마무리

 

 

직진을 우선적으로 생각해야 하는 문제

만약 최단 루트가 최단 거울 개수를 보장한다고 생각하면 무조건 틀리는 문제인 듯 싶다.

문제의 조건을 명확히 해야 한다는 것을 알게 해준 문제다