일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
- C++ 함수
- precision
- 백준C++
- 혁펜하임
- 백준
- AI강의
- 혁펜하임강의
- tensorflow
- cuDNN
- AIDEEPDIVE
- 비교연산자
- C++
- 백준1463
- 1로만들기
- 패스트캠퍼스
- pytorch
- 패스트캠퍼스혁펜하임
- 혁펜하임강의후기
- C++ 백준
- 1463
- 반복문
- C++ 공백 입력
- c++ 기초
- 백준1026
- 혁펜하임AI
- 백준9095
- CUDA
- 9095
- 조건문
- for문
- Today
- Total
코딩하는 덕구 🐶
118. [삼성기출14]Python 백준 15683 번 감시 자세한 설명 본문
안녕하세요 코딩하는 덕구입니다.
백준 15683 번 감시 입니다.
https://www.acmicpc.net/problem/15683
15683번: 감시
스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감
www.acmicpc.net
먼저 백준 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 코드였습니다.
감사합니다.
'알고리즘 문제 풀이' 카테고리의 다른 글
120. [삼성기출16]Python 백준 15685 번 드래곤 커브 자세한 설명 (0) | 2023.05.26 |
---|---|
119. [삼성기출15]Python 백준 15684 번 사다리조작 자세한 설명 (0) | 2023.05.19 |
117. [삼성기출13]Python 백준 14891 번 톱니바퀴 자세한 설명 (0) | 2023.05.09 |
116. [삼성기출12]Python 백준 14890 번 경사로 자세한 설명 (0) | 2023.04.17 |
115. [삼성기출11]Python 백준 14889 번 스타트와 링크 자세한 설명 (0) | 2023.04.14 |