문제 링크입니다: https://www.acmicpc.net/problem/6087
6087번: 레이저 통신
문제 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 설치해야 하는 거울 개수의 최솟값을 구하는 프로그램을 작성하시오. 레이저로 통신한다는 것은 두 칸을 레이저로 연결할 수 있음을 의미한다. 레이저는 C에서만 발사할 수 있고, 빈 칸에 거울('/', '\')을 설치해서 방향을 90도 회전시킬 수 있다.
www.acmicpc.net
저는 처음에 거울을 하나하나 설치하는 방법으로 접근했고 이는 당연히 TLE가 발생했습니다.
이후에 문제에 대해 곰곰히 생각해봤고 아래와 같은 알고리즘을 적용해서 간단히 풀 수 있었습니다.
1. dist[y 좌표][x 좌표][방향] 3차원 배열을 선언하고 모두 INF로 초기화합니다.
2. 두 개의 C 좌표 중 하나를 시작 좌표로 선정하고 해당 좌표를 기준으로 모든 방향에 대해 큐에 넣고 dist 배열 또한 0으로 초기화합니다.
3. 2번과 똑같은 방법으로 시작좌표에서 거울을 설치하지 않고 갈 수 있는 지점들을 모두 큐에 집어넣고 dist 배열을 0으로 초기화합니다.
4. 이제 큐에 집어넣은 좌표들을 하나씩 꺼내는데 dist 배열에는 거울이 설치된 개수가 저장되어야하므로 현재 큐 사이즈를 구한 뒤 해당 큐 사이즈만큼 반복문을 돌려 큐에 있는 지점으로부터 갈 수 있는 지점들에 대해 dist 배열을 cnt로 초기화합니다.
(cnt = 거울의 개수, 큐 사이즈 반복문을 돌린 뒤 cnt 증가)
5. 마지막으로 모든 방향에 대해 dist[도착 지점 y][도착 지점 x][방향]를 조사하고 최솟값을 출력해주면 됩니다.
개발환경:Visual Studio 2017
지적, 조언, 질문 환영입니다! 댓글 남겨주세요~
'알고리즘 > BOJ' 카테고리의 다른 글
| 백준 2467번 용액 (0) | 2019.10.21 |
|---|---|
| 백준 7785번 회사에 있는 사람 (0) | 2019.10.21 |
| 백준 1981번 배열에서 이동 (2) | 2019.10.08 |
| 백준 2957번 이진 탐색 트리 (0) | 2019.10.08 |
| 백준 2933번 미네랄 (0) | 2019.10.07 |