풀이
CCTV 의 개수에 따라서 감시 범위의 경우의 수가 주어진다. 이를 해결하기 위해 DFS 를 통해 재귀적으로 풀 수 있다.
먼저 CCTV 의 종류에 따라 감시 방향을 정의해준다. 한번에 감시할 수 있는 방향이 여러가지인 경우도 있기 때문에 각 CCTV 의 감시 방향 경우에 따라서 감시 방향을 리스트에 저장해준 뒤 경우의 수에 따라 다시 한 번 리스트로 감싸준다.
이후 입력을 받으면서 CCTV 의 종류와 좌표를 cctvs 에 저장해준 뒤 dfs 를 실행한다.
각 CCTV 의 방향과 좌표에 따라서 2 차원 배열을 수정해 줄 watch 함수를 선언한다.
이후 각 CCTV 의 종류와 2 차원 배열을 받고 CCTV 의 종류를 cam_num 변수에 저장한 뒤 cam_num 을 인덱스로 활용해 direction 에서 감시 방향의 경우의 수를 반복문을 통해 watch 함수와 dfs 를 재귀적으로 실행시킨다.
예를 들어 2 차원 배열에 2번 CCTV 와 4번 CCTV 가 있을 경우,
2번 CCTV 는 [[0, 1], [2, 3]] 로 총 2 가지 경우의 수가 있고
4번 CCTV 는 [[3, 0, 2], [1, 3, 0], [0, 2, 1], [2, 1, 3]] 로 총 4 가지 경우의 수가 있다.
이럴 경우 cctvs 에는 [[2, x, y], [4, x, y]] 가 저장될 것이다.
dfs 를 실행시키면 첫 번째 CCTV 인 2번 CCTV 에 대한 dfs 가 실행되고,
for d in direction[can_num] = for d in direction[2] = for d in [[0, 1], [2, 3]] 가 된다.
이후 d = [0, 1] 에 대한 watch 함수와 dfs 가 실행되는데 watch 에선,
for d in direction = for d in [0, 1] 이 되고 각 d 에 따라서 감시 범위를 수정한 뒤 dfs 를 실행한다.
정리하자면,
for d in [[0, 1], [2, 3]]:
watch(d)
for d in [[3, 0, 2], [1, 3, 0], [0, 2, 1], [2, 1, 3]]:
watch(d)
에 대한 2중 반복문이 실행되는 것이다.
첫 DFS 문제여서 역시 많은 코드를 참고했고 추후에 풀어볼 문제에 많은 도움이 될 것 같다.
소스코드
References