문제
크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다.
'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 설치해야 하는 거울 개수의 최솟값을 구하는 프로그램을 작성하시오. 레이저로 통신한다는 것은 두 칸을 레이저로 연결할 수 있음을 의미한다.
레이저는 C에서만 발사할 수 있고, 빈 칸에 거울('/', '\')을 설치해서 방향을 90도 회전시킬 수 있다.
아래 그림은 H = 8, W = 7인 경우이고, 빈 칸은 '.', 벽은 '*'로 나타냈다. 왼쪽은 초기 상태, 오른쪽은 최소 개수의 거울을 사용해서 두 'C'를 연결한 것이다.
7 . . . . . . . 7 . . . . . . .
6 . . . . . . C 6 . . . . . /-C
5 . . . . . . * 5 . . . . . | *
4 * * * * * . * 4 * * * * * | *
3 . . . . * . . 3 . . . . * | .
2 . . . . * . . 2 . . . . * | .
1 . C . . * . . 1 . C . . * | .
0 . . . . . . . 0 . \-------/ .
0 1 2 3 4 5 6 0 1 2 3 4 5 6입력
첫째 줄에 W와 H가 주어진다. (1 ≤ W, H ≤ 100)
둘째 줄부터 H개의 줄에 지도가 주어진다. 지도의 각 문자가 의미하는 것은 다음과 같다.
.: 빈 칸
*: 벽
C: 레이저로 연결해야 하는 칸
'C'는 항상 두 개이고, 레이저로 연결할 수 있는 입력만 주어진다.
출력
첫째 줄에 C를 연결하기 위해 설치해야 하는 거울 개수의 최솟값을 출력한다.
풀이
다익스트라를 이용하면 되는 문제이다.
가중치의 경우, 거울의 개수를 설정하면 되는데 탐색 시 규칙이 다르게 작용한다.
이동 방향을 정하고 선택한 방향으로 계속해서 움직인다.
이때, 종료 조건은 다음과 같다.
1. 벽을 만날 경우
2. 지도 밖을 벗어날 경우
3. 기존에 탐색이 완료 되었는데, 거울 개수가 같고 방향이 다른 경우
탐색 규칙도 기존 다익스트라와 다르지만 중요한 건 3번이다.
거울 개수가 같고 방향이 다른 경우, 거울을 하나 추가로 설치해야 되기 때문에 이때 탐색을 종료해야 하는 것이다.
기존에는 힙큐에 방향을 넣고 풀이하려 했으나, 리스트에는 방향이 저장되지 않는 이슈가 있어 방향을 비교하지 못하였다.
이때문에 3시간은 소요한 듯 하다... 쓸데없이 시간만 날렸다. 시간가는 줄도 몰랐네
으아아아아아악 시간 아까워
