[Python/파이썬] - 백준(BOJ) 15683번 : 감시

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

15683번: 감시

 

브루트포스를 이용한 문제.

1번 - 상하좌우

2번 - 상하

3번 - 상하좌우

4번 - 상하좌우

5번 - 한가지 경우

이렇게 번호별로 경우의 수를 나눠 그대로 짜면 된다.

기능구현을 마쳤으면 모든 경우의수를 테스트 해보면 된다.

파이썬에서 재귀함수를 사용할 때 리스트를 인자로 넘겨주고 그 리스트에 변화가 없게 하려면

from copy import deepcopy를 해주어 deepcopy를 사용해야 한다.

하지만 deepcopy는 시간이 오래 걸리기 때문에 다음에 deepcopy를 사용하지 않고 풀어봐야겠다.

 

import sys
answer = sys.maxsize
from copy import deepcopy
def watch(brr, q, v):
    global answer
    if v == len(q):
        s = 0
        for i in range(len(brr)):
            for j in range(len(brr[0])):
                if brr[i][j] == 0:
                    s += 1
        if answer > s:
            answer = s
        return

    y = queue[v][0]
    x = queue[v][1]
    dy = [0, 1, 0, -1]
    dx = [1, 0, -1, 0]
    if queue[v][2] == 1:
        for i in range(4):
            vec = i
            arr = deepcopy(brr)
            yy = y
            xx = x
            while 0 <= yy < n and 0 <= xx < m:
                if arr[yy][xx] == 0:
                    arr[yy][xx] = -1
                elif arr[yy][xx] == 6:
                    break
                yy += dy[vec]
                xx += dx[vec]
            watch(arr, q, v+1)
    elif queue[v][2] == 2:
        for i in range(2):
            vec = i
            arr = deepcopy(brr)
            for _ in range(2):
                yy = y
                xx = x
                while 0 <= yy < n and 0 <= xx < m:
                    if arr[yy][xx] == 0:
                        arr[yy][xx] = -1
                    elif arr[yy][xx] == 6:
                        break
                    yy += dy[vec]
                    xx += dx[vec]
                vec = (vec + 2) % 4
            watch(arr, q, v+1)

    elif queue[v][2] == 3:
        for i in range(4):
            vec = i
            arr = deepcopy(brr)
            for _ in range(2):
                yy = y
                xx = x
                while 0 <= yy < n and 0 <= xx < m:
                    if arr[yy][xx] == 0:
                        arr[yy][xx] = -1
                    elif arr[yy][xx] == 6:
                        break
                    yy += dy[vec]
                    xx += dx[vec]
                vec = (vec + 1) % 4
            watch(arr, q, v+1)


    elif queue[v][2] == 4:
        for i in range(4):
            vec = i
            arr = deepcopy(brr)
            for _ in range(3):
                yy = y
                xx = x
                while 0 <= yy < n and 0 <= xx < m:
                    if arr[yy][xx] == 0:
                        arr[yy][xx] = -1
                    elif arr[yy][xx] == 6:
                        break
                    yy += dy[vec]
                    xx += dx[vec]
                vec = (vec + 1) % 4
            watch(arr, q, v+1)

    elif queue[v][2] == 5:
        vec = 1
        arr = deepcopy(brr)
        for _ in range(4):
            yy = y
            xx = x
            while 0 <= yy < n and 0 <= xx < m:
                if arr[yy][xx] == 0:
                    arr[yy][xx] = -1
                elif arr[yy][xx] == 6:
                    break
                yy += dy[vec]
                xx += dx[vec]
            vec = (vec + 1) % 4
        watch(arr, q, v+1)

    return arr, v+1


if __name__ == '__main__':
    n, m = map(int,input().split())
    arr = [list(map(int,input().split())) for _ in range(n)]
    queue = []
    for i in range(n):
        for j in range(m):
            if 0 < arr[i][j] < 6:
                queue.append([i,j,arr[i][j]])
    watch(arr, queue, 0)
    print(answer)