Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- 딥러닝
- deep voice
- you only look once
- DCTTS
- 윈도우
- 한국어 tts
- Vocoder
- YOLO
- 음성 합성
- singing voice synthesis
- korean tts
- tacotron
- 딥러닝 음성 합성
- TTS
- melgan
- 한국어 음성 합성
- 딥러닝 보코더
- 노래합성
- 학습
- 트레이닝
- waveglow
- 보코더
- text-to-speech
- 타코트론
Archives
- Today
- Total
chldkato
백준 15683 감시 (파이썬) 본문
https://www.acmicpc.net/problem/15683
1. 사무실 크기를 입력받고 넓이를 area 변수에 저장한다
2. cctv 1~4는 cctv 리스트에 저장하고 cctv 5는 cctv5 리스트에 저장한다
cctv와 벽을 만나면 area에 1을 빼서 구역의 넓이를 갱신한다
3. cctv5는 4방향을 감시할 수 있으므로 먼저 처리한다
감시 가능한 구역을 -1로 표시하고 area에 1을 뺀다
4. 이제 dfs로 각 cctv의 모든 방향에 대해서 검사한다
cctv 2는 다른 cctv와 다르게 2방향에 대한 경우밖에 없지만 따로 처리하지는 않았다
5. 각 cctv가 감시할 방향을 정했으면 move함수로 감시 가능한 구역의 개수를 return 받아 c에 저장한다
6. area - c를 하면 사각 지대의 크기를 구할 수 있으므로 최소값을 구하여 출력한다
from collections import deque
from copy import deepcopy
import sys
input = sys.stdin.readline
dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]
def dfs(cnt):
global ans, temp_a
if cnt == len(cctv):
temp_a = deepcopy(a)
c = 0
for i in range(len(cctv)):
x, y = cctv[i]
if a[x][y] == 1:
c += move(x, y, dir[i])
elif a[x][y] == 2:
c += move(x, y, dir[i])
c += move(x, y, (dir[i] + 2) % 4)
elif a[x][y] == 3:
c += move(x, y, dir[i])
c += move(x, y, (dir[i] + 1) % 4)
else:
c += move(x, y, dir[i])
c += move(x, y, (dir[i] + 1) % 4)
c += move(x, y, (dir[i] + 2) % 4)
ans = min(ans, area - c)
return
for i in range(4):
dir.append(i)
dfs(cnt + 1)
dir.pop()
def move(x, y, d):
cnt = 0
while True:
nx = x + dx[d]
ny = y + dy[d]
if not 0 <= nx < n or not 0 <= ny < m or temp_a[nx][ny] == 6:
return cnt
if 0 < temp_a[nx][ny] < 6 or temp_a[nx][ny] == -1:
x, y = nx, ny
continue
temp_a[nx][ny] = -1
cnt += 1
x, y = nx, ny
n, m = map(int, input().split())
area = n * m
a, cctv, cctv5 = [], [], []
for i in range(n):
row = list(map(int, input().split()))
a.append(row)
for j in range(m):
if 0 < a[i][j] < 5:
cctv.append([i, j])
area -= 1
elif a[i][j] == 5:
cctv5.append([i, j])
area -= 1
elif a[i][j] == 6:
area -= 1
for i in range(len(cctv5)):
x, y = cctv5[i]
for i in range(4):
nx, ny = x, y
while True:
nx += dx[i]
ny += dy[i]
if not 0 <= nx < n or not 0 <= ny < m or a[nx][ny] == 6:
break
if 0 < a[nx][ny] < 6 or a[nx][ny] == -1:
continue
a[nx][ny] = -1
area -= 1
dir = deque()
ans = area
dfs(0)
print(ans)
'백준' 카테고리의 다른 글
백준 14890 경사로 (파이썬) (0) | 2020.04.16 |
---|---|
백준 14891 톱니바퀴 (파이썬) (0) | 2020.04.16 |
백준 15684 사다리 조작 (파이썬) (0) | 2020.04.15 |
백준 15685 드래곤 커브 (파이썬) (0) | 2020.04.14 |
백준 15686 치킨 배달 (파이썬) (0) | 2020.04.14 |
Comments