[BOJ] - 15683

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

완전탐색

• 가능한 모든 경우의 수를 탐색하는 유형이다
• 문제의 depth가 크지 않을 때는 재귀로 풀 수 있다
• 재귀로 푸는 문제가 많다
• 재귀의 끝 (탈출조건)에 도달했을 때, 1을 리턴해 경우의 수를 카운트한다, 또는 답을 계산해서 리턴한다 (리턴된 값을 받아 최대/최소를 업데이트 한다)
• 경우의 수, 최대, 최소를 구하는 문제는 완전탐색 유형이다
• 완전탐색을 수행하는 방법은
  • for, if 문 활용
  • DFS 를 돌리면서 depth마다 상태를 결정 또는 탐색 방향을 결정
    • 예를 들어, 상하좌우 방향으로 DFS 재귀 수행
    • 예를 들어, 특정 아이템을 선택하는경우, 선택하지 않는 경우 각각 DFS 재귀 수행
  • 비트마스크
• 재귀를 돌고 나오면 기존 상태를 복원해야한다
  

노트

1) 좌표를 다루는 방법

• dx, dy를 정의한다
• 좌표를 탐색해야하는 경우 dx, dy를 더해가며 맵 크기 바깥으로 벗어나기 전까지 탐색한다
  • 예를 들어, x, y좌표 시작점 주어지고 dx, dy방향으로 계속 값을 변경할때

    def fill(x, y, arr, dset):
    for d in dset:
        nx, ny = x, y
        while True:
        	# dx, dy를 사용해 탐색
            nx += dx[d]
            ny += dy[d]
            if 0 <= nx < n and 0 <= ny < m:
                if arr[nx][ny] == 6:
                    break
                elif arr[nx][ny] == 0:
                    arr[nx][ny] = '#'
            else:
                break

2) 상태를 복원하는 방법 2가지

• copy.deepcopy 활용

temp = copy.deepcopy(arr)
    out = sys.maxsize
    for dset in direction[ctype]:
        fill(x, y, temp, dset)
        out = min(out, solve(depth+1, temp))
        temp = copy.deepcopy(arr)

• list extend 활용
• list를 변수에 할당하는 것은 value copy 가 아니라 reference 할당이다
• 2d array는 이렇게 처리하면 안된다 (내부는 레퍼런스 전달인듯)

#
arr = [1,2,3]
arr2 = []
arr2.extend(arr)

arr2[0] = 3
print(arr2, arr) # [3, 2, 3] [1, 2, 3]

#
arr = [1,2,3]
arr3 = arr

arr3[0] = 2
print(arr3, arr) # [2, 2, 3] [2, 2, 3]

풀이

1) 좌표문제이므로 dx, dy를 정의한다
2) cctv 타입마다 회전 방향에 따라 감시하는 방향을 정의한다
3) cctv 위치를 저장해둔다
4) DFS 에서 cctv를 한개씩 꺼내서 회전방향에 따라 상태를 바꾸고, DFS 돌리고, 복원하고 동작을 반복한다

틀린 이유

1) cctv 감시 여부를 나타내는 state array를 따로 만들었었는데
그럴필요없이 처음 주어진 지도에 다른 기호로 표시했으면 됐다

2) 상태 복원을 위해 state 를 True, False 로 구현했는데,
copy.deepcopy를 사용해 상태를 복원하는게 훨씬 안전하다

3) 상태를 글로벌 변수로 사용해 관리하지 말고, copy 해서 fill함수에 넣어주고 상태를 변경했어야 했다

4) 파이썬은 list 함수 인자를 레퍼런스로 받으므로 별도의 리턴 없이 함수 내부에서 변경한게 함수 외부에서도 반영된다

def func(arr, a):
    arr[0] = 2
    a = 1

arr = [1,2,3]
a = 2

func(arr, a)

print(arr, a) # [2, 2, 3] 2

4) 풀이가 지나치게 복잡하다면 의심해보자 fill 함수처럼 간단하게 할 수 있어야한다

코드

import sys, copy

# 모든 방향 에 대해 채우는 방법에 대해 정의할 필요 없이,
# 방향이 주어지면 맵이 끝날때까지 채운다
def fill(x, y, arr, dset):
    for d in dset:
        nx, ny = x, y
        while True:
            nx += dx[d]
            ny += dy[d]
            if 0 <= nx < n and 0 <= ny < m:
                if arr[nx][ny] == 6:
                    break
                elif arr[nx][ny] == 0:
                    arr[nx][ny] = '#'
            else:
                break

def solve(depth, arr):
    if depth == len(cctv_pos):
        result = 0
        for i in range(n):
            for j in range(m):
                if arr[i][j] == 0:
                    result += 1

        return result

    x, y , ctype = cctv_pos[depth]

    # dfs 탐색 후에 탐색 전 상태로 복원하기 위해 deepcopy 사용
    temp = copy.deepcopy(arr)
    out = sys.maxsize
    for dset in direction[ctype]:
        fill(x, y, temp, dset)
        out = min(out, solve(depth+1, temp))
        temp = copy.deepcopy(arr)

    return out

sys.stdin = open('15683.txt')

n, m = list(map(int, input().split()))

data = []
for _ in range(n):
    data.append(list(map(int, input().split())))


# 아래, 위, 오른쪽, 왼쪽
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
direction = [[],[[0],[1],[2],[3]],
             [[2,3], [1,0], [3,2], [0,1]],
             [[2,1], [1,3], [3,0], [0,2]],
             [[0,1,2], [1,2,3], [0,2,3], [0,1,3]],
             [[0,1,2,3]]]

cctv_pos = []
for i in range(n):
    for j in range(m):
        if data[i][j] in [1,2,3,4,5]:
            cctv_pos.append([i,j, data[i][j]]) # (i, j, cctv type)

out = solve(0, data)

print(out)