[BOJ / 백준] 15683번 감시 파이썬(Python) 문제 풀이

문제

 

문제 링크 : https://www.acmicpc.net/problem/15683

15683번: 감시

 

 

 

 

 

CODE

import sys

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
camdir = [0, 4, 2, 4, 4, 1] # 카메라 종류별 분별 가능한 방향 수


def watch(idx, dir, office):
    if cam[idx][2] == 1:
        x, y = cam[idx][0], cam[idx][1]
        while 0 <= x < n and 0 <= y < m and office[x][y] != 6:
            if office[x][y] == 0:
                office[x][y] = 7
            x, y = x + dx[dir], y + dy[dir]

    elif cam[idx][2] == 2:
        x, y = cam[idx][0], cam[idx][1]
        while 0 <= x < n and 0 <= y < m and office[x][y] != 6:
            if office[x][y] == 0:
                office[x][y] = 7
            x, y = x + dx[dir], y + dy[dir]

        x, y = cam[idx][0], cam[idx][1]
        while 0 <= x < n and 0 <= y < m and office[x][y] != 6:
            if office[x][y] == 0:
                office[x][y] = 7
            x, y = x + dx[dir + 2], y + dy[dir + 2]

    elif cam[idx][2] == 3:
        x, y = cam[idx][0], cam[idx][1]
        while 0 <= x < n and 0 <= y < m and office[x][y] != 6:
            if office[x][y] == 0:
                office[x][y] = 7
            x, y = x + dx[dir - 1], y + dy[dir - 1]

        x, y = cam[idx][0], cam[idx][1]
        while 0 <= x < n and 0 <= y < m and office[x][y] != 6:
            if office[x][y] == 0:
                office[x][y] = 7
            x, y = x + dx[dir], y + dy[dir]

    elif cam[idx][2] == 4:
        x, y = cam[idx][0], cam[idx][1]
        while 0 <= x < n and 0 <= y < m and office[x][y] != 6:
            if office[x][y] == 0:
                office[x][y] = 7
            x, y = x + dx[dir - 2], y + dy[dir - 2]

        x, y = cam[idx][0], cam[idx][1]
        while 0 <= x < n and 0 <= y < m and office[x][y] != 6:
            if office[x][y] == 0:
                office[x][y] = 7
            x, y = x + dx[dir - 1], y + dy[dir - 1]

        x, y = cam[idx][0], cam[idx][1]
        while 0 <= x < n and 0 <= y < m and office[x][y] != 6:
            if office[x][y] == 0:
                office[x][y] = 7
            x, y = x + dx[dir], y + dy[dir]

    elif cam[idx][2] == 5:
        x, y = cam[idx][0], cam[idx][1]
        while 0 <= x < n and 0 <= y < m and office[x][y] != 6:
            if office[x][y] == 0:
                office[x][y] = 7
            x, y = x + dx[dir], y + dy[dir]

        x, y = cam[idx][0], cam[idx][1]
        while 0 <= x < n and 0 <= y < m and office[x][y] != 6:
            if office[x][y] == 0:
                office[x][y] = 7
            x, y = x + dx[dir + 1], y + dy[dir + 1]

        x, y = cam[idx][0], cam[idx][1]
        while 0 <= x < n and 0 <= y < m and office[x][y] != 6:
            if office[x][y] == 0:
                office[x][y] = 7
            x, y = x + dx[dir + 2], y + dy[dir + 2]

        x, y = cam[idx][0], cam[idx][1]
        while 0 <= x < n and 0 <= y < m and office[x][y] != 6:
            if office[x][y] == 0:
                office[x][y] = 7
            x, y = x + dx[dir + 3], y + dy[dir + 3]


def solve(cnt, off):
    global result

    if cnt == len(cam):
        temp = 0
        for i in range(n):
            temp += off[i].count(0)
        result = min(result, temp)
        return

    for i in range(camdir[cam[cnt][2]]):
        t_off = [item[:] for item in off]
        watch(cnt, i, t_off)
        solve(cnt + 1, t_off)


n, m = map(int, sys.stdin.readline().split())
office = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
result = n * m

cam = []    # 카메라 위치 저장
for i in range(n):
    for j in range(m):
        if 0 < office[i][j] < 6:
            cam.append([i, j, office[i][j]])

solve(0, office)
print(result)

 

 

 

 

 

풀이

💡 idea

- DFS로 풀어 모든 경우를 탐색하자!

- 각 카메라가 감시하는 곳을 모두 표시한다

- 카메라 종류별로 분별 가능한 방향 수는 다음과 같다

1) 4가지

2) 2가지

3) 4가지

4) 4가지

5) 1가지

 

 

💡 implementation

 

 

camdir = [0, 4, 2, 4, 4, 1]

- 카메라 종류별로 분별 가능한 방향 수

 

cam = []
for i in range(n):
    for j in range(m):
        if 0 < office[i][j] < 6:
            cam.append([i, j, office[i][j]])

- 카메라의 위치와 종류를 리스트 cam에 따로 저장하여 관리한다

 

- solve 함수 : DFS

- watch 함수 : 카메라가 감시하는 구역의 표시

 

t_off = [item[:] for item in off]

- copy.deepcopy()를 이용하여 깊은 복사를 하는 것보다 slicing하는 것이 훨씬 빠르다!

- deepcopy()를 사용한 코드는 3956ms  →  slicing을 통한 깊은 복사를 한 코드 548ms

 

📌 속도 차이에 충격 받고 파이썬에서 복사의 종류와 시간에 대해서 글로 정리했습니다!

  https://codesyun.tistory.com/198

[Python] 파이썬 리스트 복사 : 시간 초과 해결, 깊은 복사와 얕은 복사, copy, deepcopy, slicing, 2차원 리

 

 

 

 

 

결과