빛의 경로 사이클
링크
문제에 대한 이해
- 어떠한 격자에서 빛을 쏜다.
- 격자에 적힌 알파벳에 따라 이동 방향이 달라진다.
- 격자 내에서 빛이 이동할 수 있는 경로 사이클이 몇 개 있고, 각 사이클의 길이가 얼마인지 알아야 한다.
접근 방법
어떤 칸에서부터 시작해야 할까?
모르면 일단 아무 지점에서 사이클을 만들어보자. → 모든 지점에서 완전 탐색을 해보자.
- 참고로, 사이클 특성 상 가장 첫 번째 위치에서만 탐색을 하더라도 모든 사이클의 파악이 가능하다. 모든 지점, 모든 방향에 대해 방문할 수 있다.
- 동일한 사이클의 기준
- y, x 좌표에서 d 방향으로 이동한 이력이 있다면, 이미 사이클이 만들어졌다는 뜻이므로 더 이상 탐색할 필요가 없다.
- 해당 지점에서 SLR에 따른 방향으로 이동할 경우 뒤 이동 경로는 동일하기 때문이다.
탐색 방법
- 시작 지점, 시작 방향에 도착했다면 하나의 사이클이 완성된 것이다.
- 방문과 동시에 사이클의 길이를 기록할 수 있도록, visited 배열을 boolean 값으로 저장하는 것 보다는, 숫자로 저장하는 것이 좋다.
- 모든 지점 및 모든 방향에 대해 탐색할 수 있도록 3차원 배열을 준비한다.
- 모든 지점 및 방향에 대해 탐색한다. 단, 아직 방문하지 않은 지점 및 방향이어야 한다.
visited[y][x][d] == 0 - bfs 후 해당 칸의 visited 값을 배열에 추가한다.
- 오름차순으로 사이클 배열을 정렬한다.
통과 코드
배운 것
- visited 배열은 boolean 값이 아닌 int 자료형으로도 구현이 가능하다.
- 이 경우, 가장 첫 번째 방문한 지점은 방문 처리가 되지 않고 다시 돌아왔을 때 방문 처리가 되기 때문에 사이클 처리에 더 용이하다.