문제

감시

스타트링크의 사무실은 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

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

왼쪽 상단 2: ↔, 오른쪽 하단 2: ↔

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

왼쪽 상단 2: ↔, 오른쪽 하단 2: ↕

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

왼쪽 상단 2: ↕, 오른쪽 하단 2: ↔

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

왼쪽 상단 2: ↕, 오른쪽 하단 2: ↕

0 # 0 0 0 #
0 2 0 0 0 #
0 # 0 0 6 #
0 6 0 0 2 #
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개를 넘지 않는다.

출력 조건

---

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

정답 코드

---

import sys  
from copy import deepcopy  
dxs, dys = (1, 0, -1, 0), (0, 1, 0, -1)  
cctv_direction_range = {1: 4, 2: 2, 3: 4, 4: 4, 5: 1}  
  
  
n, m = map(int, sys.stdin.readline().rstrip().split())  
g = [list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(n)]  
cctv = []  
for i in range(n):  
    for j in range(m):  
        if 0 < g[i][j] < 6:  
            cctv.append((j, i, g[i][j]))  
k = len(cctv)  
ans = n * m + 1  
  
  
def in_range(a, b):  
    return 0 <= a < m and  0 <= b < n  
  
  
def proceed(a, b, office, direction):  
    dx, dy = dxs[direction], dys[direction]  
    nx, ny = a, b  
    while in_range(nx, ny) and g[ny][nx] != 6:  
        office[ny][nx] = 7  
        nx += dx  
        ny += dy  
  
  
def watch(a, b, office, cctv_num, direction):  
    proceed(a, b, office, direction)  
    if cctv_num == 2:  
        proceed(a, b, office, (direction + 2) % 4)  
    elif cctv_num == 3:  
        proceed(a, b, office, (direction + 1) % 4)  
    elif cctv_num == 4:  
        proceed(a, b, office, (direction + 1) % 4)  
        proceed(a, b, office, (direction - 1) % 4)  
    elif cctv_num == 5:  
        for d in range(1, 4):  
            proceed(a, b, office, (direction + d) % 4)  
  
  
def dfs(depth, office):  
    if depth == k:  
        global ans  
        ans = min(ans, sum([1 for a in range(m) for b in range(n) if office[b][a] == 0])) 
        return  
    a, b, num = cctv[depth]  
    for d in range(cctv_direction_range[g[b][a]]):  
        tmp_office = deepcopy(office)  
        watch(a, b, tmp_office, num, d)  
        dfs(depth + 1, tmp_office)  
  
  
dfs(0, g)  
print(ans)

풀이

---

매우 매우 귀찮은 구현 + 백트래킹 문제입니다.
CCTV 가 최대 8개로 한정되어 있고, 모든 경우의 수를 다 봐야하기 때문에 간단하게 백트래킹 문제인 거는 감을 잡았지만 CCTV가 본다는 거를 어떻게 표현하지...
여기서 살짝 고민을 했습니다.

결론은 노다가가 답이었습니다.

그럼 각 함수가 무슨 일을 하는지 우선 설명해 드리겠습니다.

1. in_range

def in_range(a, b):  
    return 0 <= a < m and  0 <= b < n 

정말 간단하게 현재 좌표가 사무실을 벗어났는지 아닌지 확인하는 함수입니다.
사실 이것도 함수화를 시켜서 밖으로 뺄까 말까를 엄청 고민했습니다.
시간 복잡도가 엄청난 문제들은 가끔 얘를 함수화를 안시키면 통과되고 (그나마도 pypy3로 했을 때...)
함수로 빼면 통과가 안되는 문제가 간혹 존재하거든요...

하지만 이 문제는 시간 복잡도가 그렇게 심하다고는 생각되지 않아서 함수로 만들어서 풀었습니다.
혹시 파이썬이나 자바로 백준에서 문제를 풀 때, 시간복잡도를 줄이고 싶으시면, 해당 함수를 제거해 보시면 약간은 좋아질 겁니다!!

2. proceed

def proceed(a, b, office, direction):  
    dx, dy = dxs[direction], dys[direction]  
    nx, ny = a, b  
    while in_range(nx, ny) and g[ny][nx] != 6:  
        office[ny][nx] = 7  
        nx += dx  
        ny += dy 

CCTV가 보고 있는 시선에 따라 감시되는 영역을 표시해주는 함수입니다.
각각 인자는 다음과 같습니다.

• a : CCTV의 x 좌표
• b : CCTV의 y 좌표
• office : 현재 사무실 상황
• direction : 현재 cctv가 보고 있는 방향

위와 같은 정보들을 받고 단순하게 한 방향으로 현재 사무실 내에서 감시 되는 영역을 표시해 주는 함수입니다.
while 문을 돌려서 계속 한 방향으로 전진시켜 줍니다.
범위는 벗어나거나(in_range), 벽을 만나면(6) 감시 영역 표시를 중단합니다.

3. watch

def watch(a, b, office, cctv_num, direction):  
    proceed(a, b, office, direction)  
    if cctv_num == 2:  
        proceed(a, b, office, (direction + 2) % 4)  
    elif cctv_num == 3:  
        proceed(a, b, office, (direction + 1) % 4)  
    elif cctv_num == 4:  
        proceed(a, b, office, (direction + 1) % 4)  
        proceed(a, b, office, (direction - 1) % 4)  
    elif cctv_num == 5:  
        for d in range(1, 4):  
            proceed(a, b, office, (direction + d) % 4)

이제 각 CCTV 번호에 맞춰서 해당되는 방향으로 감시 영역을 쏴줍니다.
각 인자를 다음과 같습니다

• a : CCTV의 x 좌표
• b : CCTV의 y 좌표
• office : 현재 사무실 상황
• cctv_num : CCTV 종류
• direction : 현재 cctv가 보고 있는 방향

앞선 proceed 함수와 인자가 거의 동일합니다.
이 하지만 CCTV는 종류마다 볼 수 있는 영역이 다르기 때문에 CCTV의 종류를 구별할 cctv_num 이 추가로 필요합니다.

CCTV를 보시면 모든 CCTV는 현재 자신의 방향은 무조건 보기 때문에
proceed를 무조건 1회 해당 방향으로 호출합니다.

그리고 각 번호에 따라 방향을 추가하면서 proceed를 호출합니다.

저는 dxs, dys = (1, 0, -1, 0), (0, 1, 0, -1) 를 보시면 알 수 있듯이
동 -> 남 -> 서 -> 북 -> 동 순서대로 방향을 설정했습니다.
그리고 불필요한 반복문 호출을 피하기 위해
cctv_direction_range = {1: 4, 2: 2, 3: 4, 4: 4, 5: 1} 를 사용했습니다.
CCTV를 잘 보시면 1, 3, 4는 4방향에 대해서 모두 탐색을 해줘야 하지만, 2는 2방향만, 5는 한 방향 만으로도 모든 경우의 수를 볼 수 있습니다.

1번 CCTV

3번 CCTV

4번 CCTV

1, 3, 4의 경우 4방향 모두 형태가 다르기 때문에 동서남북 모두를 봐야 한다

2번 CCTV

5번 CCTV

2번은 같은 모양이 2번만에 나오고 5번은 어디를 바라보면 형상이 같다

4. dfs

def dfs(depth, office):  
    if depth == k:  
        global ans  
        ans = min(ans, sum([1 for a in range(m) for b in range(n) if office[b][a] == 0])) 
        return  
    a, b, num = cctv[depth]  
    for d in range(cctv_direction_range[g[b][a]]):  
        tmp_office = deepcopy(office)  
        watch(a, b, tmp_office, num, d)  
        dfs(depth + 1, tmp_office) 

대망의 dfs입니다!!
이렇게 CCTV들을 보는 거를 구현했으니 이제 감시를 해야겠죠!!

• depth: 탐색 깊이입니다. 현재 몇 번째 cctv를 보고있는지에 활용할 변수입니다. 만약 depth가 cctv 개수와 같아지면 이제 감시되는 영역과 아닌 영역을 세고 ans를 갱신해 줍니다 만약 아니면, 그 다음 depth로 함수 dfs를 더 실행시킵니다
• office : 현재 사무실 현황입니다. DFS 방식으로 진행하기 때문에 2차원 배열을 그대로 넘겨줘야 하기 때문에 인자로 포함시켰습니다.

depth는 현재 dfs 의 진척도이자 현재 몇 번 cctv를 보고 있는지 알려주는 척도입니다.

현재 cctv의 종류에 따라 cctv_direction_range에서 알맞은 범위를 가져오고, 반복문을 돌립니다.
그리고 상황마다 다 다른 사무실 상황을 넘겨줘야 하므로 deepcopy로 완전히 복사된 사무실 tmp_office를 watch 함수를 통해 감시 영역을 갱신하고, 그 다음 dfs로 넘겨줍니다.

그리고 depth == k 즉, cctv를 전부 훑어본 경우
이제 현재 감시되지 않은 영역을 세 주고 만약 감시되지 않은 영역이 현재 ans에 저장된 값보다 작으면 (현재 감시중인 영역이 최대치) ans 를 갱신시켜줍니다.

처음에는 불안해서 pypy3로 제출했는데 생각보다 널널하게 통과해서 동일 코드로 python3로 제출했는데 통과했습니다! 기준이 많이 널널한 것 같아요!

마무리

귀찮기는 했지만, 딱히 어렵지는 않은 백트래킹 문제였습니다.
문제를 풀 때 시간복잡도 생각을 많이 안했는데도 한 번만에 통과해서 놀랐습니다.

이 문제가 삼성 기출문제 안에 들어있기는 한데...
이제 더 이상은 이렇게 쉬운 문제는 안나오겠죠ㅠㅠ