06087번 레이저 통신

Problem link: https://www.acmicpc.net/problem/06087

Keywords: Breadth first search

(여기 포스팅된 대부분의 다른 문제들도 그러하지만) 예전에 분명 풀었던 문제이고, 예전에 한 번 고생한 기억이 있는 문제인데 또 고전했다. 이런 날은 하루종일 우울한데, 그나마 정리라도 잘해놓으면 기분이 조금 나아진다.

일단 풀이는 간단한데, 아래와 같이 방문 상태를 정의한 뒤에 BFS를 사용해서 풀어주면 된다.

• VISIT[row][col][dir]: \((row, col)\) 에 \(dir\) 방향으로 진입하는 경우에 대한 방문 상태

내가 고전했던 부분은 “BFS를 진행할 때, \((row, col)\) 에서 갈 수 있는 상태들을 꼭 모두 검사해줘야 할까?” 라는 의문에서 시작되었다. 다시말하면 아래와 같은 과정을 겪었다 (물론 아래는 틀린 접근이다).

• \((row + 1, col), (row + 2, col), ...\) 따위를 꼭 한번에 넣어주어야 할까?
• 그냥 인접한 것 하나만 넣어주고 알아서 큐에서 pop 되기를 기대할 수는 없을까?
• 그런데 BFS는 큐에 넣는 순서가 중요한데…아! 그러면 우선순위 큐를 쓰고 거울 수가 작은 것 부터 뽑으면 되겠다!

과연 위의 접근에서 무엇이 잘못되었을까? 위의 접근은 (1) 전체 로직은 BFS를 유지했으나, (2) 큐만 우선순위 큐로 갈아끼운 것이 가장 문제라고 할 수 있다. “음? 그래도 되는 것 아니야?” 싶다면, Dijkstra 따위의 알고리즘을 잘 생각해보자. 이런 알고리즘에서 우선순위 큐를 사용할 때에 우리가 기대하는 것은:

• 큐에 어떤 순서로 push 하던 cost가 낮은 것 부터 pop 되는 것이지,
• 큐에 우선 순위대로 push가 이뤄지는 것은 아니다.
• 그래서, 우리는 최단거리가 갱신되는 경우에 한하여 재방문을 허용하지 않았는가?

두번째 불렛에서 큐에 우선 순위대로 (거울을 적게 쓴 순서로) push가 되는 것을 기대하는게 BFS 이기 때문에 따라서, 이 접근은 틀릴 수 밖에 없다. 아마도, 그냥 Dijkstra를 풀듯이 더 적은 갯수의 거울을 사용하는 경우에 한해서 재방문을 허용했다면 문제 없는 알고리즘이 되리라.

솔루션은 여기 에서 확인할 수 있다.