백준 15683 - 감시 (python)

평범한 대학생·2023년 2월 14일

baekjoon

목록 보기

8/12

감시 문제 보러가기

시뮬레이션 문제

BFS나 재귀와 같이 특정 자료구조 혹은 알고리즘에 종속되지 않고 주어진 문제 상황을 구현하면 되는 문제이다

구현이 빡세게 필요하다

구현력을 가지고 빠르고 정확하게 풀어내는게 관건이다.

막혔던 부분

각각의 CCTV별로 모든 방향을 고려해 경우의 수를 찾는 부분에서 막힘

즉, 공간상에 있는 모든 CCTV 방향을 고려해 경우의 수를 구해야하는데 백트래킹을 사용하면 되겠다고 생각했지만 구현하지 못함.

회전하는 것을 코드상에서 어떻게 구현할 수 있는지 생각해보기

문제를 해결하는데 사용한 방법

내가 이 문제를 분석하면서 배우게 된 점은 일단 개별 CCTV의 모든 방향을 고려해 경우의 수를 구하는 방법은 다음과 같이 2가지로 풀 수 있다는 점이었다.

백트래킹

진법 표현

핵심 포인트 요약 바로가기
참고 링크

문제

스타트링크의 사무실은 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번의 방향에 따라 감시할 수 있는 영역을 '#'로 나타내면 아래와 같다.

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

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

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

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

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

입력

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

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

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

출력

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

핵심 포인트 요약

구현해야하는 부분

CCTV는 90도 방향으로 회전시킬 수 있으므로, 1번부터 5번까지의 각각의 CCTV에 대해 가능한 모든 방향을 고려해 탐색(감시) 해야합니다 즉, 모든 CCTV에 대해 각각 회전해서 나올수 있는 모든 경우의 수을 찾아야한다는 것을 알 수 있습니다.
👉 이 경우 백트래킹으로 풀 수 있습니다. 혹시 다른 방법이 없나 찾아봤는데 진법을 이용한 방법으로도 풀 수있어 참고하시면 될것 같습니다. 참고한 링크

참고한 링크에서, 지금의 상황과 같이 변수들이 가질 수 있는 값이 여러개이고 모든 조합을 다 확인해보고 싶은데 변수들끼리는 독립적일 땐 백트래킹 보다 진법을 이용한 방법이 더 쉬운 방법이라고 설명합니다.

CCTV가 감시하는 행위는 CCTV가 감시할 수 있는 방향을 정한다음 그 방향으로 벽이 닿을때까지 또는 사무실 공간을 벗어날때까지 반복을 하면서 마크를 남기면 됩니다.

코드 & 설명 주석 포함 (진법)

from collections import deque
import sys, copy
input = sys.stdin.readline

# 사무실의 세로, 가로(N x M)
N, M = map(int, input().split())
space = [list(map(int, input().split())) for _ in range(N)]
tmp_space = copy.deepcopy(space)

# 남, 동, 북, 서 방향을 가리킴 
# 남쪽을 시작으로 반시계방향으로 돌아가는 순서로 되어 있음
dy = [1, 0, -1, 0]
dx = [0, 1, 0, -1]

# 사무실의 범위를 벗어나는지 체크해주는 함수
def check(row, col):
    return row < 0 or row >=N or col < 0 or col >=M
    
def init():
    obj = deque() # cctv의 위치를 저장할 큐 
    answer = 0
    for i in range(N):
        for j in range(M):
            # 벽이아니고 빈칸이아니면 
            if space[i][j] != 6 and space[i][j] != 0:
                obj.append((space[i][j], i, j))   
            # cctv번호, cctv y좌표, cctv x좌표 저장
            
            # cctv가 아에 없는 경우도 고려해서 빈칸의 갯수로 맞춰줌
            if space[i][j] == 0: answer += 1
    return obj, answer
    
# cctv번호와 좌표, 빈칸 개수 초기화
cctv, answer = init()

# 특정 방향을 감시한다는 것은 그 방향으로 이동하는 것으로 생각할 수 있음
# y: y축좌표, x: x축좌표, direction: 우리가 감시할 방향
def move(y, x, direction):
    direction %= 4
    while True:
        y += dy[direction]
        x += dx[direction]
        # 범위를 벗어났거나 벽을 만났다면 return
        if check(y, x) or tmp_space[y][x] == 6:
            return
        # 빈칸이아니면 
        if tmp_space[y][x] != 0:
            continue
        # 빈칸이면
        tmp_space[y][x] = '#'
        

# 각각의 cctv에 대해서 모든 방향을 고려해 모든 경우의 수를 구함
for i in range(4**len(cctv)):
    case = i
    tmp_space = copy.deepcopy(space)
    
    for j in range(len(cctv)):
        d = case % 4
        case //= 4
        
        num, y, x = cctv[j]
        
        # cctv번호 별로 가르키는 방향으로 이동함
        # 이 부분을 간결하게 작성하려면 어떻게 해야할까 (고민)
        if num == 1:
            move(y, x, d)
        elif num == 2:
            move(y, x, d); move(y, x, d+2)
        elif num == 3:
            move(y, x, d); move(y, x, d+1)
        elif num == 4:
            move(y, x, d); move(y, x, d+1); move(y, x, d+2)
        else:
            move(y, x, d); move(y, x, d+1); move(y, x, d+2); move(y, x, d+3)
    
    # 하나의 case에서 수행을 다 마치면 사각 지대의 개수를 구함
    zero_cnt = 0
    for i in tmp_space:
        zero_cnt += i.count(0)
    answer = min(zero_cnt, answer)
print(answer)

코드 & 설명 주석 포함 (백트래킹)

from collections import deque
import sys
input = sys.stdin.readline

# 사무실의 세로(N), 가로(M)
N, M = map(int, input().split())
space = [list(map(int, input().split())) for _ in range(N)]

# 남, 동, 북, 서 방향을 가리킴 (남쪽을 시작으로 반시계방향으로 돌아가는 순서로 되어 있음)
dy = [1, 0, -1, 0]       # y축
dx = [0, 1, 0, -1]       # x축

# 감시해야하는 모든 방향 (각각의 cctv별로 감시할 수 있는 방향)
direction = {
    1: [[0], [1], [2], [3]],            # 1번cctv 방향:0, 1, 2, 3, --> 4가지
    2: [[0, 2], [1, 3]],                    # 2번cctv 방향:(0, 2), (1, 3) --> 2가지
    3: [[0, 1], [1, 2], [2, 3], [3, 0]],    # 3번cctv 방향:(0, 1), (1, 2), (2, 3), (3, 0) --> 4가지
    4: [[0, 1, 2], [1, 2, 3], [2, 3, 0], [3, 0, 1]],    # 4번cctv 방향... 4가지
    5: [[0, 1, 2, 3]]                      # 5번cctv 방향... 1가지
}

# 사무실의 범위를 벗어나는지 체크해주는 함수
def check(row, col):
    return row < 0 or row >=N or col < 0 or col >=M
    

def init():
    obj = deque() #  cctv의 위치를 저장할 큐 
    answer = 0
    for i in range(N):
        for j in range(M):
            # 벽이아니고 빈칸이아니면 
            if space[i][j] != 6 and space[i][j] != 0:
                obj.append((space[i][j], i, j))   # cctv번호, cctv 좌표 저장
            # cctv가 아에 없는 경우도 고려해서 빈칸의 갯수로 맞춰둠
            if space[i][j] == 0:answer += 1
    return obj, answer

# cctv좌표들, 빈칸 개수 초기화
cctv, answer = init()


def move(y, x, direc, space_copy):
    # 각각의 방향에 대해서 전부 이동시켜줌
    for d in direc:
        ny, nx = y, x
        
        while True:
            nx += dx[d]
            ny += dy[d]
            # 범위를 벗어났거나 벽을 만났다면 
            if check(ny, nx) or space_copy[ny][nx] == 6:
                break
            # 빈칸이아니면 
            if space_copy[ny][nx] != 0:
                continue
            space_copy[ny][nx] = '#'


# 사각지대를 구하는 함수        
def zero_cnt(space_copy):
    global answer
    cnt = 0
    for i in space_copy:
        cnt += i.count(0)
    answer = min(answer, cnt) 
    

# 백준 15651 N과 M(3) 문제와 유사 (백트래킹)
def dfs(level, space):
    # space_copy = copy.deepcopy(space)           
    space_copy = [[j for j in space[i]] for i in range(N)]
    # 2번째 상태가 실행되기전 바로 전 상태를 저장함 
    # (예를 들어 2번째 상태를 시작하기 전에 1번째 상태의 결과를 저장함)
   
    if level == len(cctv):
        zero_cnt(space_copy)
        return			# 전 상태로 돌아감
    
    number, y, x  = cctv[level]
    
    # number번째 cctv에 대해 가능한 모든 방향을 순차적으로 고려 
    for d in direction[number]:    
        move(y, x, d, space_copy)
        dfs(level+1, space_copy)   # level+1번째 cctv를 고려
        space_copy = [[j for j in space[i]] for i in range(N)]
        # space_copy = copy.deepcopy(space)
        
        # 하나의 상태를 return 한다음 바로 전 상태로 바꿈 
        # 만약 2번째 상태가 끝났다면,  1번째를 수행했을 때의 결과로 바꿈
    
dfs(0, space)
print(answer)

보충 설명

진법 코드

# 만약 cctv 개수가 2개라면 
cctv_cnt = 2
for i in range(4**cctv_cnt):
    case = i
    for _ in range(cctv_cnt):
        print(case%4, end='')
        case //= 4
    print()

출력
00
10
20
30
01
11
21
...
22
32 ------> ??
03
13
23
33

👉 만약 cctv 개수가 2개일 때 진법표현으로 어떻게 경우의 수를 구할 수 있는지(접근할 수 있는지) 생각해보자.

cctv가 가리킬 수 있는 가능한 방향이 4가지 이므로 4진법을 사용

# 남, 동, 북, 서 방향을 가리킴
dy = [1, 0, -1, 0]
dx = [0, 1, 0, -1]

32 라는 숫자(4진법)가 의미하는 것은 첫번째 cctv가 가리키는 방향은 3 두번째 cctv가 가리키는 방향은 2 라는 의미로 이는 dy, dx 의 인덱스라고 생각하면 될 것같다.

백트래킹 코드
15651 N과 M(3) 와 유사

space_copy = [[j for j in space[i]] for i in range(N)]

import copy
space_copy = copy.deepcopy(space)

👉 deepcopy 를 썼을때와 안썼을 때의 속도 차이

처음엔 별차이 없을거라 생각했지만... 위쪽이 안썼을 때, 아래쪽이 썼을 때로 생각보다 차이가 많이 났다. 앞으로 최대한 안쓰는 방향으로 풀어야 할 것같다.
추가적으로 백트래킹으로 구현한 dfs 함수에서 상태를 넘나들때 space_copy 변수가 어떻게 변하는지 이해하는게 핵심이라고 생각된다.

혹시나 잘못된 부분이 있으면 댓글 부탁드립니다.