118. [삼성기출14]Python 백준 15683 번 감시 자세한 설명

안녕하세요 코딩하는 덕구입니다.

백준 15683 번 감시 입니다.

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

15683번: 감시

 

먼저 백준 15683 번 감시 정답 코드입니다. 설명은 아래에 있습니다.

import copy
n, m = map(int, input().split())
office = []
mode = [
    [],
    [[0], [1], [2], [3]],
    [[0, 2], [1, 3]],
    [[0, 1], [1, 2], [2, 3], [3, 0]],
    [[0, 1, 2], [1, 2, 3], [2, 3, 0], [3, 0, 1]],
    [[0, 1, 2, 3]],
]
cctvs = []
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

for i in range(n):
    office.append(list(map(int, input().split()))) #build office
    for j in range(m):
        if office[i][j] in [1, 2, 3, 4, 5]:
            cctvs.append([office[i][j], i, j]) #build cctv_info

def dfs(depth, arr):
    if depth == len((cctvs)):
        global ans
        cnt = 0
        for i in range(n):
            cnt += arr[i].count(0)
        ans = min(ans, cnt)
        return

    cctv_num = cctvs[depth][0]
    x = cctvs[depth][1]
    y = cctvs[depth][2]

    for mo in mode[cctv_num]:
        tmp = copy.deepcopy(arr)
        fill(tmp, mo, x, y)
        dfs(depth + 1, tmp)

def fill(graph, mode, x, y):
    for mo in mode:
        nx = x
        ny = y
        while True:
            nx += dx[mo]
            ny += dy[mo]
            if nx < 0 or ny < 0 or nx >= n or ny >= m:
                break
            if graph[nx][ny] == 6:
                break
            if graph[nx][ny] == 0:
                graph[nx][ny] = 7

ans = 1e9
dfs(0, office)
print(ans)

 

문제 접근

cctv별로 모든 방향을 확인해야 되므로 dfs를 통해 불필요한 반복을 줄입니다.

 

Python 코드 구현

 

copy : deepcopy를 사용하기 위한 모듈입니다.

deepcopy를 사용하면 원본이 변하는 것을 방지할 수 있습니다.

mode : cctv 1~5번 까지의 회전에 따른 감시할 수 있는 경우의 수를 담고 있는 리스트입니다..

office : 감시할 구역의 정보를 저장할 2차원 리스트 입니다.

cctvs : cctv들의 종류와 위치 정보를 저장할 리스트 입니다.

dx, dy : 2차원 리스트의 탐색을 구현하기 쉽게 도와주는 리스트 입니다.

import copy
n, m = map(int, input().split())
office = []
mode = [
    [],
    [[0], [1], [2], [3]],
    [[0, 2], [1, 3]],
    [[0, 1], [1, 2], [2, 3], [3, 0]],
    [[0, 1, 2], [1, 2, 3], [2, 3, 0], [3, 0, 1]],
    [[0, 1, 2, 3]],
]
cctvs = []
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

 

첫 번째 for 문에서는 office를 입력받습니다.

두 번째 for 문에서는 cctv가 있는지 탐색합니다.

cctv를 발견하면 리스트 cctvs에 cctv 번호와 좌표를 저장합니다.

for i in range(n):
    office.append(list(map(int, input().split()))) #build office
    for j in range(m):
        if office[i][j] in [1, 2, 3, 4, 5]:
            cctvs.append([office[i][j], i, j]) #build cctv_info

 

 

dfs : 사각지대의 최소값인 ans를 업데이트 하는 함수입니다.

depth : dfs의 깊이 입니다. depth가 0이면 사무실의 cctv들 중 첫 번째 cctv의 모든 경우를 확인합니다.

만약 1이라면 2번째 cctv의 모든 경우를 확인합니다.

arr : office의 상태를 의미합니다

 

if문 : 만약 깊이가 cctv개수와 같다면 (모든 cctv들의 경우를 확인했다면)

ans와 현재 상태의 사각지대의 개수를 비교해 더 작은 수를 업데이트 합니다.

 

깊이가 cctv 개수보다 작다면

현재 탐색할 cctv종류와 좌표를 입력받습니다.

그 다음 for문에서 cctv 종류별 방향을 mo에 저장합니다.

tmp에는 현재까지의 상태를 저장하고

fill 함수를 통해 감시 구역을 표시합니다.

깊이 + 1, tmp를 입력해주고 재귀적으로 dfs를 실행시켜줍니다.

def dfs(depth, arr):
    if depth == len((cctvs)):
        global ans
        cnt = 0
        for i in range(n):
            cnt += arr[i].count(0)
        ans = min(ans, cnt)
        return

    cctv_num = cctvs[depth][0]
    x = cctvs[depth][1]
    y = cctvs[depth][2]

    for mo in mode[cctv_num]:
        tmp = copy.deepcopy(arr)
        fill(tmp, mo, x, y)
        dfs(depth + 1, tmp)

 

fill : 감시가능 구역을 사각지대를 의미하는 0이 아닌 7로 채웁니다.

감시 방향을 입력받고 해당 방향으로

1. office의 범위를 벗어나거나

2. 벽을 만날때 까지

감시구역으로 표시합니다.

def fill(graph, mode, x, y):
    for mo in mode:
        nx = x
        ny = y
        while True:
            nx += dx[mo]
            ny += dy[mo]
            if nx < 0 or ny < 0 or nx >= n or ny >= m:
                break
            if graph[nx][ny] == 6:
                break
            if graph[nx][ny] == 0:
                graph[nx][ny] = 7

 

파이썬 백준 15683 번 감시 최종 코드입니다. 

import copy
n, m = map(int, input().split())
office = []
mode = [
    [],
    [[0], [1], [2], [3]],
    [[0, 2], [1, 3]],
    [[0, 1], [1, 2], [2, 3], [3, 0]],
    [[0, 1, 2], [1, 2, 3], [2, 3, 0], [3, 0, 1]],
    [[0, 1, 2, 3]],
]
cctvs = []
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

for i in range(n):
    office.append(list(map(int, input().split()))) #build office
    for j in range(m):
        if office[i][j] in [1, 2, 3, 4, 5]:
            cctvs.append([office[i][j], i, j]) #build cctv_info

def dfs(depth, arr):
    if depth == len(cctvs):
        global ans
        cnt = 0
        for i in range(n):
            cnt += arr[i].count(0)
        ans = min(ans, cnt)
        return

    cctv_num = cctvs[depth][0]
    x = cctvs[depth][1]
    y = cctvs[depth][2]

    for mo in mode[cctv_num]:
        tmp = copy.deepcopy(arr)
        fill(tmp, mo, x, y)
        dfs(depth + 1, tmp)

def fill(graph, mode, x, y):
    for mo in mode:
        nx = x
        ny = y
        while True:
            nx += dx[mo]
            ny += dy[mo]
            if nx < 0 or ny < 0 or nx >= n or ny >= m:
                break
            if graph[nx][ny] == 6:
                break
            if graph[nx][ny] == 0:
                graph[nx][ny] = 7

ans = 1e9
dfs(0, office)
print(ans)

 

백준 15683 번  감시 자세한 설명 및 Python 코드였습니다.

감사합니다.