[BaekJoon] 15683번 : 감시

15683번 : 감시

너무나 당연하게 감시 범위가 넓은 CCTV 순으로 감시할 수 있는 최대 범위를 감시해가며 계산을 했는데 바로 틀렸다.

무조건 최대 범위를 감시하는 게 옳은 방법이 아니었던 것이다.

결국 CCTV가 감시할 수 있는 모든 경우를 따져 그중 사각지대가 최소일 때를 반환해야 한다.

만약 1번, 2번 CCTV가 각각 한 대씩 있었다고 하면 총 8 가지의 경우가 나온다.

1번이 위쪽을 감시하며 2번이 좌 우, 상 하 인 경우

1번이 오른쪽을 감시하며 2번이 좌 우, 상 하 인 경우

1번이 아래쪽을 감시하며 2번이 좌 우, 상 하 인 경우

1번이 왼쪽을 감시하며 2번이 좌 우, 상 하 인 경우

그런데.. 풀이 방법은 알았는데 이걸 코드로 바꾸자니 도저히 모르겠어서 다른 사람의 코드를 참고했다

https://qrlagusdn.tistory.com/150

내가 생각했던 풀이 방법을 코드로 보니 배울 점이 정말 많이 있었다.

특히 CCTV가 바라보는 모든 경우를 재귀로 해결한 부분이 인상 깊었다.

처음엔 이해가 안가 디버깅을 엄청 했다..

배운 게 많이 있는 문제였다 시간이 지나고 다시 꼭 풀어야 할 문제 1순위이다.

---

import copy
from collections import Counter

#  상, 하, 좌, 우
dir_i = [-1, 1, 0, 0]
dir_j = [0, 0, -1, 1]
detection_dir = [0, [[0], [1], [2], [3]], [[0, 1], [2, 3]], [[1, 2], [1, 3], [0, 2], [0, 3]],
	  [[0, 1, 2], [0, 1, 3], [0, 2, 3], [1, 2, 3]], [[0, 1, 2, 3]]]

MIN = float("INF")


def solution(cctv_idx, office, cctv_list):
	global MIN

	if cctv_idx == len(cctv_list):
		detection_area = Counter(sum(office, []))[0]
		MIN = min(MIN, detection_area)
		return

	cctv_num, cctv_i, cctv_j = cctv_list[cctv_idx]
	for cctv_dir in detection_dir[cctv_num]:
		tmp_office = copy.deepcopy(office)
		for i in cctv_dir:
			visit_i = cctv_i + dir_i[i]
			visit_j = cctv_j + dir_j[i]
			while 0 <= visit_i < n and 0 <= visit_j < m:
				if tmp_office[visit_i][visit_j] == 6:
					break
				elif tmp_office[visit_i][visit_j] == 0:
					tmp_office[visit_i][visit_j] = 9
				visit_i += dir_i[i]
				visit_j += dir_j[i]
		solution(cctv_idx + 1, tmp_office, cctv_list)


if __name__ == "__main__":
	n, m = map(int, input().rsplit())
	office = [list(map(int, input().rsplit())) for _ in range(n)]
	cctv_list = []
	for i in range(n):
		for j in range(m):
			if office[i][j] not in [0, 6]:
				cctv_list.append([office[i][j], i, j])

	solution(0, office, cctv_list)
	print(MIN)