백준 15683 감시 (Python)

문제

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

나의 접근법

먼저 그리디 인지 DFS인지 고민을 했습니다.

cctv의 번호가 높을 수록 많은 범위를 감시하는 것 같아서 그리디로 먼저 풀었습니다. 그래서 번호가 높은 cctv를 역으로 정렬하여 탐색했습니다.

하지만 그리디로 풀 경우 현재 값이 다음 값에 영향을 받을 수 있다는 것을 office를 출력해서 알게 되었습니다. 

 

DFS로 작성하기 위해서는 원래의 office에 #을 추가한 office을 따로 구분해야 했습니다.

또한 #을 추가한 office을 임시로 저장하고 DFS 탐색이 끝난 뒤 return 했을 때, 또 새로운 office를 DFS 단계에 넘겨줘야 하는데 여기서 해답을 찾지 못했습니다.

마지막으로 cctv 번호 별로 방향을 구분 짓지 못해서 위, 아래, 오른쪽, 왼쪽을 탐색하는 함수를 각각 만들어 줬습니다.

하지만 이렇게 작성을 하니 코드의 가독성이 너무 떨어지고 결과가 나오지 못했습니다. 

이렇게 계속 제 코드를 고집하는 것보단 빨리 정답 코드를 보고 제 코드의 틀린점을 찾고 어떻게 깔끔하게 작성했는지 공부하기 위해 구글링을 하였습니다.

작성 코드

import sys
from collections import deque
N, M = map(int, sys.stdin.readline().split())
office = []
cctvList = []

def checkTop(i, j, tempOff):
    result = 0
    if i < 0: return result #사무실 바깥일때
    for k in range(i, -1, -1):
        if tempOff[k][j] == 6: return # 벽
        elif tempOff[k][j] != 0: continue #다른 cctv
        else:
            tempOff[k][j] = -1
            result += 1
    return [result, tempOff]

def checkBottom(i, j, tempOff):
    result = 0
    if i > N: return result
    for k in range(i, N):
        if tempOff[k][j] == 6: #벽
            return [result, tempOff]
        elif tempOff[k][j] != 0: #다른 cctv
            continue
        else:
            result += 1
            tempOff[k][j] = -1
    return [result, tempOff]

def checkRight(i, j, tempOff):
    result = 0
    if j > M: return result
    for k in range(j, M):
        if tempOff[i][k] == 6: #벽
            return [result, tempOff]
        elif tempOff[i][k] != 0: #다른 cctv
            continue
        else:
            result += 1
            tempOff[i][k] = -1
    return [result, tempOff]

def checkLeft(i, j, tempOff):
    result = 0
    if j < 0: return result  # 사무실 바깥일때
    for k in range(j, -1, -1):
        if tempOff[i][k] == 6: #벽
            return [result, tempOff]
        elif tempOff[i][k] != 0: #다른 cctv
            continue
        else:
            result += 1
            tempOff[i][k] = -1
    return [result, tempOff]

def sol(office, cctvList):
    num, i, j = cctvList.pop(0)
    ans = 0
    if num == 5:
        temp, office = checkTop(i-1, j, office) + checkBottom(i + 1, j, office) + checkRight(i, j + 1, office) + checkLeft(i, j - 1, office)
        ans += temp
    elif num == 4:
        officeList = []
        tempOff1 = [i[:] for i in office]
        tempOff2 = [i[:] for i in office]
        tempOff3 = [i[:] for i in office]
        tempOff4 = [i[:] for i in office]

        officeList.append(checkTop(i - 1, j, office) + checkRight(i, j + 1, office) + checkBottom(i + 1, j, office))
        officeList.append(checkRight(i, j + 1, office) + checkBottom(i + 1, j, office) + checkLeft(i, j - 1, office))
        officeList.append(checkBottom(i + 1, j, office) + checkLeft(i, j - 1, office) + checkTop(i - 1, j, office))
        officeList.append(checkLeft(i, j - 1, office) + checkTop(i - 1, j, office) + checkRight(i, j + 1, office))

        officeList.sort(key = lambda x:(-x[0]))

        ans += officeList[0][0]

    elif num == 3:
        officeList = []
        officeList.append(checkTop(i - 1, j, office) + checkRight(i, j + 1, office))
        officeList.append(checkRight(i, j + 1, office) + checkBottom(i + 1, j, office))
        officeList.append(checkBottom(i + 1, j, office) + checkLeft(i, j - 1, office))
        officeList.append(checkLeft(i, j - 1, office) + checkTop(i - 1, j, office))

        officeList.sort(key=lambda x: (-x[0]))
        ans += officeList[0][0]

    elif num == 2:
        officeList = []
        officeList.append(checkTop(i - 1, j, office) + checkBottom(i + 1, j, office))
        officeList.append(checkRight(i, j + 1, office) + checkLeft(i, j - 1, office))
        officeList.sort(key=lambda x: (-x[0]))
        ans += officeList[0][0]

    elif num == 1:
        officeList = []
        officeList.append(checkTop(i - 1, j, office))
        officeList.append(checkRight(i, j + 1, office))
        officeList.append(checkBottom(i + 1, j, office))
        officeList.append(checkLeft(i, j - 1, office))

        officeList.sort(key=lambda x: (-x[0]))
        ans += officeList[0][0]

    return ans

zero = 0
for i in range(N):
    office.append(list(map(int, sys.stdin.readline().split())))
    for j in range(M):
        if 0 < office[i][j] < 6:
            cctvList.append([office[i][j], i, j])
        if office[i][j] == 0:
            zero += 1

cctvList.sort(key = lambda x : (-x[0]))
print(cctvList)

result = sol(office, cctvList)
print(zero - result)

정답 코드

import sys
n, m = map(int, sys.stdin.readline().split())
cctv = []
office = []
rotate = [
    [],
    [[0], [1], [2], [3]],
    [[0, 2], [1, 3]],
    [[0, 1], [1, 2], [2, 3], [0, 3]],
    [[0, 1, 2], [0, 1, 3], [1, 2, 3], [0, 2, 3]],
    [[0, 1, 2, 3]],
]

# 북 동 남 서
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

for i in range(n):
    office.append(list(map(int, sys.stdin.readline().split())))
    for j in range(m):
        if 0 < office[i][j] < 6:
            cctv.append([office[i][j], i, j])

def check(board, cctvSight, x, y):
    for i in cctvSight:
        nx = x
        ny = y
        while True:
            nx += dx[i]
            ny += dy[i]
            if nx < 0 or ny < 0 or nx >= n or ny >= m:
                break
            if board[nx][ny] == 6:
                break
            elif board[nx][ny] == 0:
                board[nx][ny] = 7

def dfs(depth, office):
    global min_value
    if depth == len(cctv):
        count = 0
        for i in range(n):
            count += office[i].count(0)
        min_value = min(min_value, count)
        return
    temp = [i[:] for i in office]
    cctv_num, x, y = cctv[depth]
    for i in rotate[cctv_num]:
        check(temp, i, x, y)
        dfs(depth+1, temp)
        temp = [i[:] for i in office]

min_value = int(1e9)
dfs(0, office)
print(min_value)

제가 어디서 막혔는지 제대로 파악할 수 있었고 위 문제를 DFS로 깔끔하게 작성하는 방법을 배울 수 있었습니다.

일단 cctv의 개수만큼 DFS를 탐색합니다.

그런데 임의의 DFS 단계에서 cctv 번호의 가능한 모든 방향을 탐색하는 것이 아니라 한번에 탐색가능한 방향만 감시하고 바로 DFS로 넘어갔습니다.

또한 temp라는 그래프 정보도 함께 넣어주는데 대신 원래의 그래프는 영향이 가지 않게 깊은 복사로 그래프를 새로 만들어 넣어주었습니다.

DFS는 위와 같이 작성해야 깔끔한데 저는 아래 문제점들로 인해 DFS를 어려워 했습니다.

1. DFS의 끝이 어디인지 모른다.
2. 새로운 그래프를 넣어야할지 말아야할지 모른다.
3. DFS의 다음 단계로 넘어갈 때 (더 깊숙한 레벨을 탐색할 때), 탐색을 어디까지 해야하는지 감이 안잡힌다.

이러한 문제점을 파악하니 다음 비슷한 문제가 발생하면 다시 한번 도전하고 싶다는 생각이 들었고 풀 수 있다는 자신감이 생겼습니다.

다음에는 스스로 위와 비슷한 문제를 맞춰보도록 하겠습니다.

 

참고로 위 문제는 백준에서 구현, 완전탐색, 시뮬레이션으로 분류되지만 저는 DFS가 더 맞는 것 같아서 DFS로 분류했습니다.