[Python - Simulation] 15683 - 감시

📌 문제

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

1번	2번	3번	4번	5번

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

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

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

0 0 2 0 3
0 6 0 0 0
0 0 6 6 0
0 0 0 0 0

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

# # 2 # 3
0 6 # 0 #
0 0 6 6 #
0 0 0 0 #

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

📌 입력

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

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

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

📌 출력

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

📌 문제 풀이

👨‍🏫 접근

처음에는 백트래킹으로 문제를 풀어야 하는 줄 알았다. 그렇지만, 백트래킹으로 풀어도 회전 방향이 4가지 밖에 안 되고 그마저도 겹치는 방향이 존재하기 때문에 복잡도가 줄어든다. 그리고 맵의 크기도 최대 64이고, cctv도 8개가 최대이기 때문에 주어진 시간 내에 가까스로 풀 수 있다.

 

1. 백트래킹

첫 번째 방법은 백트래킹으로 푼 방법이다.

 

먼저 가능한 CCTV 유형의 모든 방향을 다 저장해주었다. 모든 방향은 아래와 같다.

# 좌 우 상 하 순서로
direction = [[],
             [(-1, 0, 0, 0), (0, 0, -1, 0), (0, 1, 0, 0), (0, 0, 0, 1)],  # 1번
             [(-1, 1, 0, 0), (0, 0, -1, 1)],  # 2번
             [(0, 1, -1, 0), (0, 1, 0, 1), (-1, 0, 0, 1), (-1, 0, -1, 0)],  # 3번
             [(-1, 1, -1, 0), (0, 1, -1, 1), (-1, 1, 0, 1), (-1, 0, -1, 1)],  # 4번
             [(-1, 1, -1, 1)]  # 5번
             ]

이렇게 하여, 해당 cctv의 모든 방향에 대해서 반복을 진행해주는 것이다.

 

본격적으로 재귀를 시작하기 전에 종료 조건을 정해주는 것이 좋다. 여기서의 종료 조건은, 모든 cctv를 다 조회했을 때이다. 그래서 종료조건은 아래와 같이 설정했다.

 

def dfs(idx, rest, origin_map):
    global area
    if idx == cctv_amount:
        area = min(area, rest)
        return

 

여기서 area는 남은 사각지대이다. 그리고 cctv를 순서대로 받았을 때, 그 순서를 지정하는 변수가 idx이다. idx가 모든 cctv를 다 순회했다면, return으로 해당 재귀 스택에서 나오는 것이다.

 

그 다음으로는 반복을 어떻게 할지(혹은 재귀를 어떻게 들어갈지) 세팅해준다. 이번에는 idx 번째 cctv의 모든 방향을 순회하면서 그 방향을 바라볼 때의 맵을 저장해서 재귀를 깊이 들어가준다.

for d in direction[int(cctvs[idx][2])]:
    next_map, next_rest = check(
        origin_map, int(cctvs[idx][0]), int(cctvs[idx][1]), d, rest)
    dfs(idx + 1, next_rest, next_map)

 

그 다음은, 영역 체킹이다. cctv는 같은 cctv, 이미 감시하고 있는 영역, 감시할 영역을 제외하고 벽이 존재할 때, 그 뒤의 영역은 절대 관찰하지 못한다. 그래서 맵에서 6을 만나면 반복을 취소해야 한다. 그래서 조건을 아래와 같이 설정할 수 있다.

for i in range(4):
        if d[i] != 0:
            if i in [0, 1]:
                ny = y + d[i]
                while 0 <= ny < m:
                    if tmp[x][ny] == '6':
                        break
                    if tmp[x][ny] == '0':
                        rest -= 1
                        tmp[x][ny] = '#'
                    ny += d[i]
            else:
                nx = x + d[i]
                while 0 <= nx < n:
                    if tmp[nx][y] == '6':
                        break
                    if tmp[nx][y] == '0':
                        rest -= 1
                        tmp[nx][y] = '#'
                    nx += d[i]

 

이렇게 해서 문제를 풀 수 있다.

 

2. 단순 반복 

하지만 곰곰히 생각해봤을 때, cctv의 감시 영역은 다음 cctv의 감시에 영향을 미치지 않기 때문에 굳이 백트래킹으로 모두 검사할 필요는 없다. 각 cctv의 최대 영역일 때만 고려하면 되는 것이다. 해당 풀이는 아직 시도하지 못해서 다음에 풀이해봐야겠다.

👨‍🏫 문제 풀이

📄 전체 코드

import sys
import copy
input = sys.stdin.readline

n, m = map(int, input().split())
# 좌 우 상 하 순서로
direction = [[],
             [(-1, 0, 0, 0), (0, 0, -1, 0), (0, 1, 0, 0), (0, 0, 0, 1)],  # 1번
             [(-1, 1, 0, 0), (0, 0, -1, 1)],  # 2번
             [(0, 1, -1, 0), (0, 1, 0, 1), (-1, 0, 0, 1), (-1, 0, -1, 0)],  # 3번
             [(-1, 1, -1, 0), (0, 1, -1, 1), (-1, 1, 0, 1), (-1, 0, -1, 1)],  # 4번
             [(-1, 1, -1, 1)]  # 5번
             ]

'''
graph: 맵
cctvs: cctv 좌표
area: 감시할 공간 개수
'''
graph = []
cctvs = []
area = 0

for i in range(n):
    row = list(input().rstrip().split())
    graph.append(row)
    for j in range(m):
        if row[j] == '0':  # 가능한 공간을 모두 저장함.
            area += 1
        elif row[j] != '6':
            cctvs.append((i, j, row[j]))

cctv_amount = len(cctvs)

# 매번 방향을 돌리면서 탐색
'''
시간 복잡도 줄이기
📌 백트래킹 -> 단순 반복
# - cctv는 서로 영향을 미치지 않으므로 모든 cctv가 최대한 많이 감시할 때 다음 cctv로 넘어감
  - 문제는 다음 cctv에서 최적의 cctv방향을 찾는 것
    -> 임시 변수를 두어서 해결?
'''


def check(graph, x, y, d, rest):
    tmp = copy.deepcopy(graph)  # 원본 값 보존을 위해 깊은 복사

    for i in range(4):
        if d[i] != 0:
            if i in [0, 1]:
                ny = y + d[i]
                while 0 <= ny < m:
                    if tmp[x][ny] == '6':
                        break
                    if tmp[x][ny] == '0':
                        rest -= 1
                        tmp[x][ny] = '#'
                    ny += d[i]
            else:
                nx = x + d[i]
                while 0 <= nx < n:
                    if tmp[nx][y] == '6':
                        break
                    if tmp[nx][y] == '0':
                        rest -= 1
                        tmp[nx][y] = '#'
                    nx += d[i]
    return tmp, rest


def dfs(idx, rest, origin_map):
    global area
    if idx == cctv_amount:
        area = min(area, rest)
        return

    for d in direction[int(cctvs[idx][2])]:
        next_map, next_rest = check(
            origin_map, int(cctvs[idx][0]), int(cctvs[idx][1]), d, rest)
        dfs(idx + 1, next_rest, next_map)


dfs(0, area, graph)
print(area)

📄 준비

import sys
import copy
input = sys.stdin.readline

n, m = map(int, input().split())
# 좌 우 상 하 순서로
direction = [[],
             [(-1, 0, 0, 0), (0, 0, -1, 0), (0, 1, 0, 0), (0, 0, 0, 1)],  # 1번
             [(-1, 1, 0, 0), (0, 0, -1, 1)],  # 2번
             [(0, 1, -1, 0), (0, 1, 0, 1), (-1, 0, 0, 1), (-1, 0, -1, 0)],  # 3번
             [(-1, 1, -1, 0), (0, 1, -1, 1), (-1, 1, 0, 1), (-1, 0, -1, 1)],  # 4번
             [(-1, 1, -1, 1)]  # 5번
             ]

'''
graph: 맵
cctvs: cctv 좌표
area: 감시할 공간 개수
'''
graph = []
cctvs = []
area = 0

for i in range(n):
    row = list(input().rstrip().split())
    graph.append(row)
    for j in range(m):
        if row[j] == '0':  # 가능한 공간을 모두 저장함.
            area += 1
        elif row[j] != '6':
            cctvs.append((i, j, row[j]))

cctv_amount = len(cctvs)

# 매번 방향을 돌리면서 탐색
'''
시간 복잡도 줄이기
📌 백트래킹 -> 단순 반복
# - cctv는 서로 영향을 미치지 않으므로 모든 cctv가 최대한 많이 감시할 때 다음 cctv로 넘어감
  - 문제는 다음 cctv에서 최적의 cctv방향을 찾는 것
    -> 임시 변수를 두어서 해결?
'''

📄 풀이

def check(graph, x, y, d, rest):
    tmp = copy.deepcopy(graph)  # 원본 값 보존을 위해 깊은 복사

    for i in range(4):
        if d[i] != 0:
            if i in [0, 1]:
                ny = y + d[i]
                while 0 <= ny < m:
                    if tmp[x][ny] == '6':
                        break
                    if tmp[x][ny] == '0':
                        rest -= 1
                        tmp[x][ny] = '#'
                    ny += d[i]
            else:
                nx = x + d[i]
                while 0 <= nx < n:
                    if tmp[nx][y] == '6':
                        break
                    if tmp[nx][y] == '0':
                        rest -= 1
                        tmp[nx][y] = '#'
                    nx += d[i]
    return tmp, rest


def dfs(idx, rest, origin_map):
    global area
    if idx == cctv_amount:
        area = min(area, rest)
        return

    for d in direction[int(cctvs[idx][2])]:
        next_map, next_rest = check(
            origin_map, int(cctvs[idx][0]), int(cctvs[idx][1]), d, rest)
        dfs(idx + 1, next_rest, next_map)


dfs(0, area, graph)
print(area)

📌 총평

조금 어려웠다. 그런데 문제 티어는 골드 4였다. ㅠㅠ 알고리즘 안 푼지 너무 오래됐나보다. 다시 시작하자! 특히 아쉬웠던 것은 구현력이 많이 부족했던 것이었다. 이부분을 중점으로 보완하자.