[Python] 백준 15683 감시

1. 문제 링크

https://www.acmicpc.net/problem/15683

15683번: 감시

2. 문제 요약

사각지대의 최소 크기를 출력

3. 아이디어 정리

1. 각 cctv 모든 경우의 수 구하기 ⇒ 각 경우 별 감시 가능한 좌표를 모두 구한다.
2. 백트래킹으로 모든 경우의 조합을 탐색한다.
   • 최댓값인 경우 갱신한다.

 

4. 문제 풀이

4-1. 내풀이

def watch(x, y, dir):
    """
    해당 방향으로 보기
    :return:
    """
    set_ = set()
    for d in dir:
        nx, ny = x, y
        while True:
            nx += dx[d]
            ny += dy[d]
            if nx < 0 or ny < 0 or nx >= n or ny >= m:  # 범위 넘어가면 그만 탐색
                break
            if graph[nx][ny] == 6:                      # 벽이면 그만 탐색
                break
            if graph[nx][ny] == 0:
                set_.add((nx, ny))
    return set_

def dfs(count, all_):
    """
    백트래킹으로 모든 방향 조합
    :return:
    """
    global  max_
    if count == len(cctv_watch):  # 최댓값인지 확인하기
        max_ = max(max_, len(all_))
        return

    for i in cctv_watch[count]:
        dfs(count + 1, all_.union(i))

# 북, 동, 남, 서
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

n, m = map(int, input().split()) # 세로, 가로
graph = [list(map(int, input().split())) for _ in range(n)]
cctv_watch = list()   # 각 cctv가 확인 가능한 좌표를 저장
zero = 0
max_ = 0

for i in range(n):
    for j in range(m):
        if graph[i][j] == 0:
            zero += 1
                # 각 cctv가 확인 가능한 좌표를 모두 확인 
        if graph[i][j] == 1:    # 한 방향, 4가지 경우 존재
            cctv_watch.append([watch(i, j, [0]), watch(i, j, [1]), watch(i, j, [2]), watch(i, j, [3])])
        elif graph[i][j] == 2:  # 서로 반대 방향
            cctv_watch.append([watch(i, j, [0, 2]), watch(i, j, [1, 3])])
        elif graph[i][j] == 3:  # 직각
            cctv_watch.append([watch(i, j, [0, 1]), watch(i, j, [1, 2]), watch(i, j, [2, 3]), watch(i, j, [3, 0])])
        elif graph[i][j] == 4:  # 3 방향
            cctv_watch.append([watch(i, j, [0, 1, 2]), watch(i, j, [1, 2, 3]), watch(i, j, [2, 3, 0]),  watch(i, j, [3, 0, 1])])
        elif graph[i][j] == 5:  # 4방향
            cctv_watch.append([watch(i, j, [0, 1, 2, 3])])

dfs(0, set())
print(zero - max_)

 

 

5. 결론

• 구현 문제