[백준 15683] 감시 (Python)

www.acmicpc.net/problem/15683

15683번: 감시

 

문제풀이

N, M, board : 입력값

cctv, cctv_n : CCTV 좌표 리스트, CCTV 개수

ans : 최소 사각지대 개수

check : 방문 여부 확인

 

재귀를 이용해 모든 CCTV를 4방향 돌리면서 감시 가능 영역을 만들어보는 브루트포스 방식으로 해결할 수 있다.

 

1. CCTV 좌표 및 개수 세주기

 

2. 재귀를 이용해 모든 CCTV의 감시 영역 탐색하기

- CCTV 종류에 따라서 방향 다르게 감시 영역 확인

- 1번 CCTV : 현재 방향

- 2번 CCTV : 현재 방향 + 반대 방향

- 3번 CCTV : 현재 방향 + 왼쪽 90도 방향

- 4번 CCTV : 현재 방향 + 반대 방향 + 왼쪽 90도 방향

- 5번 CCTV : 4방향

- 방향 설정 후 해당 방향으로 벽이나 리스트 끝에 도달할 때 까지 방문

- 벽이나 리스트 끝에 도달하면 다음 CCTV 재귀호출

- 모든 CCTV 탐색 후 사각지대 개수 확인

 

코드

import sys
from collections import deque

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

def solution(cnt):
    global check, ans
    if cnt == cctv_n: # 모든 CCTV 탐색했다면 사각지대 개수 세주기
        tmp = 0
        for i in range(N):
            for j in range(M):
                if not board[i][j] and not check[i][j]:
                    tmp += 1
        return tmp
    x, y = cctv[cnt][0], cctv[cnt][1]
    for k in range(4): # CCTV 의 4방향 확인
        new_dir = []
        if board[x][y] == 1: # 1번 CCTV : 현재 방향
            new_dir.append(k)
        elif board[x][y] == 2: # 2번 CCTV : 현재 방향 + 반대 방향
            new_dir.append(k)
            new_dir.append((k + 2) % 4)
        elif board[x][y] == 3: # 3번 CCTV : 현재 방향 + 왼쪽 90도 방향
            new_dir.append(k)
            new_dir.append((k - 1) % 4)
        elif board[x][y] == 4: # 4번 CCTV : 현재 방향 + 반대 방향 + 왼쪽 90도 방향
            new_dir.append(k)
            new_dir.append((k - 1) % 4)
            new_dir.append((k + 2) % 4)
        elif board[x][y] == 5: # 5번 CCTV : 4방향
            new_dir.append(k)
            new_dir.append((k - 1) % 4)
            new_dir.append((k + 1) % 4)
            new_dir.append((k + 2) % 4)
        q = deque()
        for d in new_dir: # CCTV 방향 개수 만큼 이동
            nx, ny = x + dx[d], y + dy[d]
            while 0 <= nx < N and 0 <= ny < M: # 특정 방향으로 끝까지 이동
                if not check[nx][ny] and board[nx][ny] != 6: # 방문하지 않았으며 벽이 아니면
                    check[nx][ny] = True # 방문
                    q.append((nx, ny))
                elif board[nx][ny] == 6: break # 벽이면 중단
                nx += dx[d]
                ny += dy[d]
        # 다음 CCTV 호출
        ans = min(ans, solution(cnt + 1))
        # 방문했던 곳 되돌려주기
        while q:
            qx, qy = q.popleft()
            if not board[qx][qy]:
                check[qx][qy] = False
        # 5번 CCTV 는 회전할 필요 없으므로 바로 break
        if board[x][y] == 5: break
    return ans

if __name__ == '__main__':
    N, M = map(int,sys.stdin.readline().split())
    board = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
    cctv = []
    cctv_n = 0 # 전체 CCTV 개수
    ans = 0 # 사각지대
    check = [[False] * M for _ in range(N)] # 방문 여부 확인
    for i in range(N):
        for j in range(M):
            if board[i][j] and board[i][j] != 6:
                cctv.append((i, j))
                check[i][j] = True
                cctv_n += 1
            if not board[i][j]:
                ans += 1 # 최대 사각지대 구하기
    solution(0)
    print(ans)

 

결과

 

문제풀이나 코드에서 이상한 부분 지적은 언제나 환영합니다!