[BOJ] 15683 감시

date

Aug 5, 2023

slug

boj-15683

author

status

Public

문제 링크

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

문제

스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감시할 수 있는 방법은 다음과 같다.

1번 CCTV는 한 쪽 방향만 감시할 수 있다. 2번과 3번은 두 방향을 감시할 수 있는데, 2번은 감시하는 방향이 서로 반대방향이어야 하고, 3번은 직각 방향이어야 한다. 4번은 세 방향, 5번은 네 방향을 감시할 수 있다.

CCTV는 감시할 수 있는 방향에 있는 칸 전체를 감시할 수 있다. 사무실에는 벽이 있는데, CCTV는 벽을 통과할 수 없다. CCTV가 감시할 수 없는 영역은 사각지대라고 한다.

CCTV는 회전시킬 수 있는데, 회전은 항상 90도 방향으로 해야 하며, 감시하려고 하는 방향이 가로 또는 세로 방향이어야 한다.


0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 0 6 0
0 0 0 0 0 0

지도에서 0은 빈 칸, 6은 벽, 1~5는 CCTV의 번호이다. 위의 예시에서 1번의 방향에 따라 감시할 수 있는 영역을 '#'로 나타내면 아래와 같다.

`0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 # 6 0 0 0 0 0 0 0`	`0 0 0 0 0 0 0 0 0 0 0 0 # # 1 0 6 0 0 0 0 0 0 0`	`0 0 # 0 0 0 0 0 # 0 0 0 0 0 1 0 6 0 0 0 0 0 0 0`	`0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 6 0 0 0 # 0 0 0`
→	←	↑	↓

CCTV는 벽을 통과할 수 없기 때문에, 1번이 → 방향을 감시하고 있을 때는 6의 오른쪽에 있는 칸을 감시할 수 없다.


0 0 0 0 0 0
0 2 0 0 0 0
0 0 0 0 6 0
0 6 0 0 2 0
0 0 0 0 0 0
0 0 0 0 0 5

위의 예시에서 감시할 수 있는 방향을 알아보면 아래와 같다.

`0 0 0 0 0 # # 2 # # # # 0 0 0 0 6 # 0 6 # # 2 # 0 0 0 0 0 # # # # # # 5`	`0 0 0 0 0 # # 2 # # # # 0 0 0 0 6 # 0 6 0 0 2 # 0 0 0 0 # # # # # # # 5`	`0 # 0 0 0 # 0 2 0 0 0 # 0 # 0 0 6 # 0 6 # # 2 # 0 0 0 0 0 # # # # # # 5`	`0 # 0 0 0 # 0 2 0 0 0 # 0 # 0 0 6 # 0 6 0 0 2 # 0 0 0 0 # # # # # # # 5`
왼쪽 상단 2: ↔, 오른쪽 하단 2: ↔	왼쪽 상단 2: ↔, 오른쪽 하단 2: ↕	왼쪽 상단 2: ↕, 오른쪽 하단 2: ↔	왼쪽 상단 2: ↕, 오른쪽 하단 2: ↕

CCTV는 CCTV를 통과할 수 있다. 아래 예시를 보자.

위와 같은 경우에 2의 방향이 ↕ 3의 방향이 ←와 ↓인 경우 감시받는 영역은 다음과 같다.

사무실의 크기와 상태, 그리고 CCTV의 정보가 주어졌을 때, CCTV의 방향을 적절히 정해서, 사각 지대의 최소 크기를 구하는 프로그램을 작성하시오.

문제풀이

CCTV가 감시 할 수 있는 방향을 모두 구해주면된다.

CCTV가 감시할 수 있는 방향의 최대값을 취해 Greedy하게 구하면 되면 틀린다.

그래서 1 ≤ N, M ≤ 8 인것을 보고 모든경우의수를 탐색하는 브루트 포스 + 백트래킹으로 풀었다.

우선 최적화를 생각해서

5같은경우에는 처음에 greedy하게 처리를 해줘도 된다. ( 4방향 모두 탐색하는 것이기 때문에 의미가 없음 )

그리고 N*N = 64의 0의 개수를 모두 탐색하는 것 보다

탐색할때 0 을 #으로 바꾼것을 기록한 것을 파라미터로 넘겨서

N만큼 탐색했을떄 ( 더이상 탐색할 수 없을때 ) 0으로 바꾼 change_count를 처음 기록한 zero_count에서

빼준것이 최소가 되게끔 코드를 짰다.

한 가지 실수를 한 것이.

DFS를 호출할 떄 cur_index → cur_index + 1* 4 을 호출하게 하면 되는데 (cur_index → cur_index + 1 * 4)에 cur_index를 1씩 증가시킨것을 추가로 호출하게하여,

불필요한 연산이 너무 늘어나서, 예제에 시간초과가 났었다.

파이썬 문제풀이 코드


import copy

N, M = map(int, input().split())

arr = []

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

cctv_list = []
for i in range(N):
    arr.append(list(map(int, input().split()))) # 입력
    
for i in range(N):
    for j in range(M):
        if arr[i][j] == 0 or arr[i][j] == 6 or arr[i][j] == '#':
            continue
        elif arr[i][j] == 5: # 5는 회전할 필요없으니 전처리
            for c in range(4): 
                multiplier = 0
                while True:
                    multiplier += 1
                    nx = j + dx[c] * multiplier
                    ny = i + dy[c] * multiplier
                    if 0 <= nx < M and 0 <= ny < N: # 범위
                        if arr[ny][nx] == 6: # 벽이면 
                            break # 벽이여도 멈춤
                        elif arr[ny][nx] == 0:
                            arr[ny][nx] = '#'
                    else:
                        break # 넘어가면 멈춤
        else:
            cctv_list.append([i, j, arr[i][j]]) #동쪽 부터 시작
            

zero_count = 0
for i in range(N):
    for j in range(M):
        if arr[i][j] == 0:
            zero_count += 1

min_square = zero_count
change_count = 0
def process(temp_arr, i, j, c, d):
    count = 0
    if c == 1: # 한 쪽만 볼 수 있음
        multiplier = 0
        while True:
            multiplier += 1
            nx = j + dx[d] * multiplier
            ny = i + dy[d] * multiplier
            if 0 <= nx < M and 0 <= ny < N: # 범위
                if temp_arr[ny][nx] == 6: # 벽이면 
                    break # 벽이여도 멈춤
                elif temp_arr[ny][nx] == 0:
                    temp_arr[ny][nx] = '#'
                    count += 1
            else:
                break # 넘어가면 멈춤
            
    if c == 2: # 앞 뒤
        for idx in [d, (d+2)%4]:
            multiplier = 0
            while True:
                multiplier += 1
                nx = j + dx[idx] * multiplier
                ny = i + dy[idx] * multiplier
                if 0 <= nx < M and 0 <= ny < N: # 범위
                    if temp_arr[ny][nx] == 6: # 벽이면 
                        break # 벽이여도 멈춤
                    elif temp_arr[ny][nx] == 0:
                        temp_arr[ny][nx] = '#'
                        count += 1
                else:
                    break # 넘어가면 멈춤
                
    if c == 3: # 앞, 오른쪽 ,(0,1), (1,2), (2,3), (3,0)
        for idx in [d, (d+1)%4]:
            multiplier = 0
            while True:
                multiplier += 1
                nx = j + dx[idx] * multiplier
                ny = i + dy[idx] * multiplier
                if 0 <= nx < M and 0 <= ny < N: # 범위
                    if temp_arr[ny][nx] == 6: # 벽이면 
                        break # 벽이여도 멈춤
                    elif temp_arr[ny][nx] == 0:
                        temp_arr[ny][nx] = '#'
                        count += 1
                else:
                    break # 넘어가면 멈춤
        
    if c == 4: # 앞, 왼쪽, 오른쪽 ,(0,1,3), (1,2,0), (2,3,1), (3,0,1)
        for idx in [d, (d+1)%4, (d+3)%4]:
            multiplier = 0
            while True:
                multiplier += 1
                nx = j + dx[idx] * multiplier
                ny = i + dy[idx] * multiplier
                if 0 <= nx < M and 0 <= ny < N: # 범위
                    if temp_arr[ny][nx] == 6: # 벽이면 
                        break # 벽이여도 멈춤
                    elif temp_arr[ny][nx] == 0:
                        temp_arr[ny][nx] = '#'
                        count += 1
                else:
                    break # 넘어가면 멈춤
                
    return temp_arr, count
        
def check(temp_arr, cur, change_count):
    global min_square
    if cur == len(cctv_list):
        min_square = min(min_square, zero_count-change_count)
        # [print(*temp_arr[i]) for i in range(len(temp_arr))]
        # print()
        return
                
    # for idx in range(cur, len(cctv_list)):
    i, j, c = cctv_list[cur]
    for d in range(4):
        temp_arrt = copy.deepcopy(temp_arr)        
        temp_arrt, count = process(temp_arrt, i, j, c, d)
        check(temp_arrt, cur+1, change_count+count)           
        
    
    
# debug
# [print(*arr[i]) for i in range(len(arr))]
# print(cctv_list)

check(arr, 0, 0)
print(min_square)

시간복잡도

O(4^N) # backtracking brute-force

입력

첫째 줄에 사무실의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 8)

둘째 줄부터 N개의 줄에는 사무실 각 칸의 정보가 주어진다. 0은 빈 칸, 6은 벽, 1~5는 CCTV를 나타내고, 문제에서 설명한 CCTV의 종류이다.

CCTV의 최대 개수는 8개를 넘지 않는다.

출력

첫째 줄에 사각 지대의 최소 크기를 출력한다.

예제 입력


4 6
0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 0 6 0
0 0 0 0 0 0

예제 출력


6 6
0 0 0 0 0 0
0 2 0 0 0 0
0 0 0 0 6 0
0 6 0 0 2 0
0 0 0 0 0 0
0 0 0 0 0 5

알고리즘 분류

구현

브루트포스 알고리즘

시뮬레이션

백트래킹