[python] 15683. 감시

문제 출처

15683. 감시

 

풀이

DFS deepcopy (0% 시간초과)

 

from copy import deepcopy

N, M = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]
cameras = [[] for _ in range(5)]
for y in range(N):
    for x in range(M):
        if 0 < arr[y][x] < 6:
            cameras[arr[y][x]-1].append((y, x))

c1_w = [[1], [2], [3], [4]]
c2_w = [[1, 3], [2, 4]]
c3_w = [[1, 2], [2, 3], [3, 4], [4, 1]]
c4_w = [[1, 2, 3], [2, 3, 4], [3, 4, 1], [4, 1, 2]]

def watch(arr, lst, y, x):
    if 1 in lst:
        for ny in range(y-1, -1, -1):   # 북
            if arr[ny][x] == 6:
                break
            if arr[ny][x]:
                continue
            arr[ny][x] = '#'
    if 2 in lst:
        for nx in range(x+1, M):        # 동
            if arr[y][nx] == 6:
                break
            if arr[y][nx]:
                continue
            arr[y][nx] = '#'
    if 3 in lst:
        for ny in range(y+1, N):        # 남
            if arr[ny][x] == 6:
                break
            if arr[ny][x]:
                continue
            arr[ny][x] = '#'
    if 4 in lst:
        for nx in range(x-1, -1, -1):   # 서
            if arr[y][nx] == 6:
                break
            if arr[y][nx]:
                continue
            arr[y][nx] = '#'
    return arr


def dfs(arr, c1_n, c2_n, c3_n, c4_n):
    global min_

    if c1_n:
        for d_lst in c1_w:
            y, x = c1[c1_n-1]
            brr = deepcopy(arr)
            brr = watch(brr, d_lst, y, x)
            dfs(brr, c1_n-1, c2_n, c3_n, c4_n)

    if c2_n:
        for d_lst in c2_w:
            y, x = c2[c2_n-1]
            brr = deepcopy(arr)
            brr = watch(brr, d_lst, y, x)
            dfs(brr, c1_n, c2_n-1, c3_n, c4_n)

    if c3_n:
        for d_lst in c3_w:
            y, x = c3[c3_n-1]
            brr = deepcopy(arr)
            brr = watch(brr, d_lst, y, x)
            dfs(brr, c1_n, c2_n, c3_n-1, c4_n)

    if c4_n:
        for d_lst in c4_w:
            y, x = c4[c4_n-1]
            brr = deepcopy(arr)
            brr = watch(brr, d_lst, y, x)
            dfs(brr, c1_n, c2_n, c3_n, c4_n-1)

    cnt = 0
    for y in range(N):
        for x in range(M):
            if arr[y][x] == 0:
                cnt += 1

    if cnt < min_:
        min_ = cnt
    return


c1, c2, c3, c4, c5 = cameras
min_ = 64

while c5:
    y, x = c5.pop()
    watch(arr, [1, 2, 3, 4], y, x)

dfs(arr, len(c1), len(c2), len(c3), len(c4))
print(min_)

 

DFS visited (21% 시간초과)

 

N, M = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]
data = [[] for _ in range(6)]
for y in range(N):
    for x in range(M):
        if arr[y][x]:
            data[arr[y][x]-1].append((y, x))

c1_w = [[1], [2], [3], [4]]
c2_w = [[1, 3], [2, 4]]
c3_w = [[1, 2], [2, 3], [3, 4], [4, 1]]
c4_w = [[1, 2, 3], [2, 3, 4], [3, 4, 1], [4, 1, 2]]

def watch(visited, lst, y, x):
    temp = []
    if (y, x) not in visited:
        temp.append((y, x))

    if 1 in lst:
        for ny in range(y-1, -1, -1):   # 북
            if arr[ny][x] == 6:
                break
            if (ny, x) not in temp and (ny, x) not in visited:
                temp.append((ny, x))
    if 2 in lst:
        for nx in range(x+1, M):        # 동
            if arr[y][nx] == 6:
                break
            if (y, nx) not in temp and (y, nx) not in visited:
                temp.append((y, nx))
    if 3 in lst:
        for ny in range(y+1, N):        # 남
            if arr[ny][x] == 6:
                break
            if (ny, x) not in temp and (ny, x) not in visited:
                temp.append((ny, x))
    if 4 in lst:
        for nx in range(x-1, -1, -1):   # 서
            if arr[y][nx] == 6:
                break
            if (y, nx) not in temp and (y, nx) not in visited:
                temp.append((y, nx))
    return temp


def dfs(visited, c1_n, c2_n, c3_n, c4_n):
    global max_

    if c1_n:
        for d_lst in c1_w:
            y, x = c1[c1_n-1]
            nxt = watch(visited, d_lst, y, x)
            dfs(visited+nxt, c1_n-1, c2_n, c3_n, c4_n)

    if c2_n:
        for d_lst in c2_w:
            y, x = c2[c2_n-1]
            nxt = watch(visited, d_lst, y, x)
            dfs(visited+nxt, c1_n, c2_n-1, c3_n, c4_n)

    if c3_n:
        for d_lst in c3_w:
            y, x = c3[c3_n-1]
            nxt = watch(visited, d_lst, y, x)
            dfs(visited+nxt, c1_n, c2_n, c3_n-1, c4_n)

    if c4_n:
        for d_lst in c4_w:
            y, x = c4[c4_n-1]
            nxt = watch(visited, d_lst, y, x)
            dfs(visited+nxt, c1_n, c2_n, c3_n, c4_n-1)
    cnt = len(visited)

    if cnt > max_:
        max_ = cnt
    return


c1, c2, c3, c4, c5, wall = data
max_ = 0
visited = []
while c5:
    y, x = c5.pop()
    visited += watch(visited, [1, 2, 3, 4], y, x)

dfs(visited, len(c1), len(c2), len(c3), len(c4))
print(M*N-max_-len(wall))

 

DFS check index(정답)

 

N, M = map(int, input().split())
arr = [[6]*(M+2)]
for _ in range(N):
    arr.append([6] + list(map(int, input().split())) + [6])
arr.append([6]*(M+2))
brr = [[0]*(M+2) for _ in range(N+2)]

cctvs = []
dx, dy = (0, 1, 0, -1), (-1, 0, 1, 0)
T, R, B, L = 1, 2, 4, 8

direct = [
    [0],
    [T, R, B, L],
    [T|B, R|L],
    [T|R, R|B, B|L, L|T],
    [T|R|B, R|B|L, B|L|T, L|T|R],
    [T|R|B|L]
]

for y in range(N+2):
    for x in range(M+2):
        if arr[y][x] == 6:
            brr[y][x] = 1
        elif arr[y][x]:
            cctvs.append((x, y, arr[y][x]))

def watch(x, y, d, o):
    for k in range(4):
        if d & (1 << k):
            nx, ny = x, y
            while arr[ny][nx] != 6:
                brr[ny][nx] += o
                nx, ny = nx+dx[k], ny+dy[k]

def dfs(cctv_num):
    global min_

    if cctv_num == len(cctvs):
        blind = 0
        for y in range(1, N+1):
            blind += brr[y].count(0)
        min_ = min(min_, blind)
        return

    x, y, cctv = cctvs[cctv_num]
    for d in direct[cctv]:
        watch(x, y, d, 1)
        dfs(cctv_num+1)
        watch(x, y, d, -1)

min_ = M*N
dfs(0)
print(min_)