A. 문제설명
2151번: 거울 설치
첫째 줄에 집의 크기 N (2 ≤ N ≤ 50)이 주어진다. 다음 N개의 줄에는 N개의 문자로 집에 대한 정보가 주어진다. ‘#’는 문이 설치된 곳으로 항상 두 곳이며, ‘.’은 아무 것도 없는 것으로 빛은 ��
www.acmicpc.net
문제에 대한 자세한 설명은 링크 참조
1. N*N 크기의 땅이 존재
2. 각 배열의 엔트리에는 '.', '!', '#', '*'가 주어짐
3. '*'는 벽으로 빛이 이동하지 못하고, '.'은 아무것도 없는 공간으로 빛이 이동가능하며 '#'은 문으로 빛이 들어오는 지점임
4. 여기서 '!'는 거울이 있는 지점인데 거울을 45도 비스듬하게 놓아 빛의 이동경로를 바꿔줌
5. 주어진 배열의 땅에서 거울을 최소로 사용하여 빛을 문에서 문으로 이동시키는 경우를 구하라
B. 접근법
DFS
문제 조건이 까다로워 보이지만, DFS로 정리하여 풀 수 있다. 여기서 유의해야 할 문제 조건들은 아래와 같다.
1. 빛이 문에서 문으로 이동하는 경우는 무조건 존재
2. 거울의 설치는 빛의 방향을 좌/우로 90도 회전시킬 수 있음
> 여기서 두번째 조건이 모호하게 작성되어 헷갈릴 수 있으나 거울을 45도 기울여 비스듬하게 설치한다고 했지 어느방향으로 고정한다는 설명은 없었다. 따라서 거울이 설치되는 경우는 수평에서 좌로 45도 기울이거나 우로 45도 기울이는 경우를 모두 고려하여 구현해주면 된다.
C. 풀이
1. DFS는 방향과 좌표정보를 가지고 탐사를 계속 진행
2. cnt가 최소 거울 갯수를 초과하면 탐사를 종료한다(가지치기)
3. 영역을 벗어나거나 *을 만나면 종료
4. #을 만나면 해당 cnt를 최소에 업데이트
5. .을 만나면 방향 그대로 이동 진행
6. !를 만나면 거울을 설치하는/안하는 경우로 dfs 분기
D. 내 코드
