[BOJ] 2344 - 거울

문제 출처

[BOJ] 2344 - 거울

 

풀이

주어진 상자에 구멍이 뚫려있고 구명으로 빛이 들어오는데 들어옵니다. 빛이 들어와서 상자 안의 거울에 부딪쳐 다른 구멍으로 나가게 되는데 나가는 구멍의 번호를 구하는 문제였습니다.

 

배열의 저장형태

상자의 구조를 배열에 저장할 때 1, 1의 좌표에서부터 저장해주고 상자 주변배열에 1부터 2N+2M까지의 번호를 저장해주었습니다.

 

구조를 만들어준 뒤 각 번호에서 시작해서 bfs로 상자 안을 탐색해 나가는 구멍을 찾아주었습니다.

 

구멍을 이동하는 빛의 움직임은 대칭적입니다. 

예를 들어 1번 구멍 -> 8번 구멍 이런 빛의 경로가 있다면 8번 구멍 -> 1번 구멍 으로 빛이 나아간다는 것입니다.

저는 이를 이용해서 dfs로 빛이 어떤 구멍으로 나가는지 찾아줄 때 모든 구멍을 돌지 않고 반만 돌려주었습니다. 위의 예제로 살펴보면 1~5까지의 구멍에서 시작한 빛이 도달하는 구멍만 탐색하였습니다.

 

코드

GitHub - small-j/Algorithm