[백준] 15683번 : 감시

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

15683번: 감시

dfs 로 모든 경우를 탐색하는 브루트포스로 풀었다 

그런데 코드가 내가 봐도 안예쁘긴하다 다시 리팩토링해봐야겠다 

함수를 애용하자 ㅎㅎ ;;

import sys
import copy

sys.setrecursionlimit(10**6)

n, m = map(int, input().split())
array = []
total = 0
answer = int(1e9)
camera = []

visited = [[False] * m for _ in range(n)]

for i in range(n):
    data = list(map(int, input().split()))
    array.append(data)
    for j in range(m):
        if data[j] == 0:
            total += 1
            
        if 1 <= data[j] <= 5:
            camera.append((i, j, data[j])) # (x, y, type)

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def simulate(count, index):
    global dx, dy 
    global answer, total, visited
    
    if index == len(camera):
        answer = min(total-count, answer)
        return 
    if total-count <= 0:
        answer = 0 
        return 

    x, y, type = camera[index]
    if type == 1:
        for i in range(4):
            temp_visited = copy.deepcopy(visited)
            temp = 0
            nx = x
            ny = y 
            while True:
                nx += dx[i]
                ny += dy[i]
                if 0 <= nx < n and 0 <= ny < m:
                    if array[nx][ny] == 0:
                        if not visited[nx][ny]:
                            visited[nx][ny] = True 
                            temp += 1
                    elif array[nx][ny] == 6:
                        break # 벽 만나면 중단
                    else: #카메라 
                        visited[nx][ny] = True 
                else:
                    break 
            simulate(count+temp, index+1)
            visited = temp_visited    
    elif type == 2:
        for data in [(0, 1), (2,3)]:
            # visited 
            temp_visited = copy.deepcopy(visited)
            temp = 0 
            for i in data:
                nx = x
                ny = y 
            
                while True:
                    nx += dx[i]
                    ny += dy[i]
                    if 0 <= nx < n and 0 <= ny < m:
                        if array[nx][ny] == 0:
                            if not visited[nx][ny]:
                                visited[nx][ny] = True 
                                temp += 1
                        elif array[nx][ny] == 6:
                            break # 벽 만나면 중단
                        else: #카메라 
                            visited[nx][ny] = True 
                    else:
                        break 
                
            simulate(count+temp, index+1)
            visited = temp_visited # reset해주기 
    elif type == 3:
        for data in [(0, 2), (0,3), (1,2), (1,3)]:
            # visited 
            temp_visited = copy.deepcopy(visited)
            temp = 0 
            for i in data:
                nx = x
                ny = y 
            
                while True:
                    nx += dx[i]
                    ny += dy[i]
                    if 0 <= nx < n and 0 <= ny < m:
                        if array[nx][ny] == 0:
                            if not visited[nx][ny]:
                                visited[nx][ny] = True 
                                temp += 1
                        elif array[nx][ny] == 6:
                            break # 벽 만나면 중단
                        else: #카메라 
                            visited[nx][ny] = True 
                    else:
                        break 
                
            simulate(count+temp, index+1)
            visited = temp_visited # reset해주기 
        
    elif type == 4:
        for data in [(0, 1, 2), (0, 1, 3), (0, 2, 3), (1, 2, 3)]:
            # visited 
            temp_visited = copy.deepcopy(visited)
            temp = 0 
            for i in data:
                nx = x
                ny = y 
            
                while True:
                    nx += dx[i]
                    ny += dy[i]
                    if 0 <= nx < n and 0 <= ny < m:
                        if array[nx][ny] == 0:
                            if not visited[nx][ny]:
                                visited[nx][ny] = True 
                                temp += 1
                        elif array[nx][ny] == 6:
                            break # 벽 만나면 중단
                        else: #카메라 
                            visited[nx][ny] = True 
                        
                    else:
                        break 
                
            simulate(count+temp, index+1)
            visited = temp_visited # reset해주기 
    else: #type == 5
        temp = 0
        for i in range(4):
            nx = x
            ny = y 
            while True:
                nx += dx[i]
                ny += dy[i]
                if 0 <= nx < n and 0 <= ny < m:
                    if array[nx][ny] == 0:
                        if not visited[nx][ny]:
                            visited[nx][ny] = True 
                            temp += 1
                    elif array[nx][ny] == 6:
                        break # 벽 만나면 중단
                    else: #카메라 
                        visited[nx][ny] = True 
                else:
                    break 
     
        simulate(count+temp, index+1)
 

simulate(0, 0)
    
print(answer)