[백준][BFS/DFS][백트래킹][deepcopy] 15638.감시

15638.감시

 

 

• 내 풀이
  • bfs

* 앞의 cctv의 경우에 이어서 다음 cctv의 경우를 다 확인해봐야함 
* cctv는 cctv를 지나갈 수 있다(중요!!)

• • cctv 위치 모두 받아놓기
  • 다음 위치에서도 같은 방향으로 이동해야하기 때문에 dir랑 같이 전송
  • cctv 가 하나도 없을 때 (0이나 6만 있음 -> 6갯수 세주기)

from copy import deepcopy
from collections import deque

n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]

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

# cctv가 지나갈때마다 변경되는 그래프 구하기
def bfs(i, j, now_graph, xlst, ylst):
    visited = [[False for _ in range(m)] for _ in range(n)]
    visited[i][j] = True

    queue = deque()

    # 다음 위치에서도 같은 방향으로 이동해야하기 때문에 dir랑 같이 전송
    for k in range(len(xlst)):
        queue.append((i, j, k))

    while queue:
        p, q, dir = queue.popleft()

        nx = p+xlst[dir]
        ny = q+ylst[dir]

        if nx < 0 or ny < 0 or nx >= n or ny >= m:
            continue

        if visited[nx][ny] == True:
            continue

        # cctv는 cctv를 지나갈 수 있다(중요!!)
        if now_graph[nx][ny] in (-1, 1, 2, 3, 4, 5):
            queue.append((nx, ny, dir))
            continue

        if now_graph[nx][ny] == 0:
            now_graph[nx][ny] = -1
            visited[nx][ny] = True
            queue.append((nx, ny, dir))

    return now_graph

# 각 cctv가 지나갈 수 있는 모든 경우 진행해보기
def track(i, j, new_graph):
    cctv_num = new_graph[i][j]
    tmp_lst = []

    for xlst, ylst in zip(dx[cctv_num], dy[cctv_num]):
        # 각 방향마다의 이동값 x,y
        # 각 방향으로 이동할때마다의 결과 그래프 추가
        tmp_lst.append(bfs(i, j, deepcopy(new_graph), xlst, ylst))

    return tmp_lst


# cctv 위치 모두 받아놓기
cctv_lst = []
for i in range(n):
    for j in range(m):
        if graph[i][j] == 0:
            continue
        if graph[i][j] == 6:
            continue
        cctv_lst.append((i, j))

# cctv 가 하나도 없을 때 (0이나 6만 있음 -> 6갯수 세주기)
if not cctv_lst:
    cnt = 0
    for i in range(n):
        cnt += graph[i].count(0)
    print(cnt)
    exit()


graph_queue = deque()
graph_queue.append(deepcopy(graph))
# 앞의 cctv의 경우에 이어서 다음 cctv의 경우를 다 확인해봐야함
for cctv in cctv_lst:
    i, j = cctv
    tmp_lst = []

    # 여기서 graph_queue는 앞의 cctv가 지나간 모든 경우의 수를 포함
    while graph_queue:
        gq = graph_queue.popleft()

        tmp_lst += track(i, j, gq)

    for tmp in tmp_lst:
        graph_queue.append(tmp)

ans = float('inf')
# 각 결과 그래프에서 최솟값 구하기
for new_graph in graph_queue:
    cnt = 0
    for i in range(n):
        for j in range(m):
            if new_graph[i][j] == 0:
                cnt += 1

    ans = min(ans, cnt)

print(ans)

 

 

• 다른 사람 풀이
  • 백트래킹, dfs
  • 내가 하나하나 직접 초기화해준 부분을 dfs와 백트래킹 통해서 간단하게 구현

import copy
n, m = map(int, input().split())
cctv = []
graph = []
mode = [
    [],
    [[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):
    data = list(map(int, input().split()))
    graph.append(data)
    for j in range(m):
        if data[j] in [1, 2, 3, 4, 5]:
            cctv.append([data[j], i, j])

def fill(board, mm, x, y):
    for i in mm:
        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, arr):
    global min_value

    if depth == len(cctv):
        count = 0
        for i in range(n):
            count += arr[i].count(0)
        min_value = min(min_value, count)
        return
    temp = copy.deepcopy(arr)
    cctv_num, x, y = cctv[depth]
    for i in mode[cctv_num]:
        fill(temp, i, x, y)
        dfs(depth+1, temp)
        temp = copy.deepcopy(arr)


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