A. 문제설명
6087번: 레이저 통신
크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서
www.acmicpc.net
문제에 대한 자세한 설명은 링크 참조
1. W*H 크기의 배열이 주어짐
2. 각 배열은 빈칸 '.' 혹은 벽 '*' 으로 이루어짐
3. 여기서 'C'로 표시되는 두 칸이 주어짐
4. 아래 그림과 같이 이 두칸을 레이저로 통신할 수 있게 잇고자 하는데 중간에 거울을 놓아 레이저의 이동방향을 90도 회전할 수 있게 함
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 65. 두 'C'를 연결하기 위해 놓아야 하는 거울의 최소값을 구하라
B. 접근법
BFS
먼저 나는 일반적인 BFS로 배열의 매 엔트리마다 직진과 좌/우회전 방향을 탐사하도록 시도하였으나 시간초과로 실패하고 말았다. 여기서 W, H의 최대값이 100이기 때문에 모든 방향에 거울을 놓고 빼고를 전부 탐사하며 이동하는 전략은 비싸서 실패한 것이다.
그러다 Rebas 블로그(rebas.kr/789)의 풀이를 따라하여 알고리즘을 고쳐보게 되었다. 개선된 BFS 탐사전략은 다음과 같다. 1. 레이저는 벽이나 배열의 경계바깥을 만나기 전까지, 계속 직선이동하며 새로운 배열에 거울 값(초기 0)을 쓴다. 2. 그러다 벽이나 경계바깥 배열을 만나면 좌/우 방향으로 90도 꺾어서 다시 이동하는데, 이때 이전 거울 값 + 1을 계산하여 거울이 놓일 수 있는 상황을 계수한다. 여기서 이미 새 배열에 값이 쓰인 경우는 제외한다.
.......
......C
......*
*****.*
....*..
....*..
.C..*..
.......위 예제를 새 배열(cnt[][])에 쓴 값은 아래와 같다.
2222221
1111112
2222220
0000020
4444023
4444023
4444023
3333323(1,6)의 'C'에서 출발하여 (6,1)의 'C'까지 도달시 총 3번의 회전이 발생한 것을 알 수 있다. 이에 따라 우리는 매 엔트리를 모두 $3^{W*H}$번 계산할 필요없이 훨씬 더 적은 비용으로 모든 배열의 탐사가 가능하다.
C. 풀이
1. 레이저는 벽이나 배열의 경계바깥을 만나기 전까지, 계속 직선이동하며 새로운 배열에 거울 값을 쓰며 BFS 큐에 넣음
2. 벽이나 경계바깥 배열을 만나면 좌/우 방향으로 90도 꺾어서 다시 이동
3. 이때, 이전 거울 값 + 1을 계산하여 거울이 놓일 수 있는 상황을 계수
4. 최종적으로 cnt[][] 배열이 모두 채워지면 목적지 'C' 위치에서 -1한 값 출력
D. 내 코드
