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 |
Tags
- 한국어 tts
- waveglow
- 트레이닝
- 학습
- 딥러닝
- 타코트론
- text-to-speech
- you only look once
- 한국어 음성 합성
- deep voice
- 노래합성
- Vocoder
- melgan
- korean tts
- 음성 합성
- TTS
- YOLO
- 딥러닝 보코더
- tacotron
- 윈도우
- 딥러닝 음성 합성
- singing voice synthesis
- DCTTS
- 보코더
Archives
- Today
- Total
chldkato
백준 1389 케빈 베이컨의 6단계 법칙 (파이썬) 본문
https://www.acmicpc.net/problem/1389
1389번: 케빈 베이컨의 6단계 법칙
첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻이다. A와 B가 친구이면, B와 A도 친구이며, A와 B가 같은 경우는 없다. 친구 관계는 중복되어 들어올 수도 있으며, 친구가 한 명도 없는 사람은 없다. 또, 모든 사람은 친구 관계로 연결되어져 있다.
www.acmicpc.net
1. 관계를 양방향으로 저장한다
2. bfs로 모든 경우에 대하여 케빈 베이컨의 수를 구한 후 최소값을 출력
from collections import deque
def bfs(x):
q.append(x)
c = [-1 for _ in range(n)]
c[x] = 0
while q:
x = q.popleft()
for i in a[x]:
if c[i] == -1:
c[i] = c[x] + 1
q.append(i)
cnt = 0
for i in range(n):
if c[i] != -1:
cnt += c[i]
return cnt
n, m = map(int, input().split())
a = [[] for _ in range(n)]
q, res, ans = deque(), [], []
for _ in range(m):
x, y = map(int, input().split())
x -= 1; y -= 1
a[x].append(y)
a[y].append(x)
for i in range(n):
res.append(bfs(i))
for i in range(n):
if res[i] == min(res):
ans.append(i)
print(min(ans)+1)
혹은 플로이드-와샬로 모든 경로를 구한 후 최소값을 출력해도 된다
import sys
INF = sys.maxsize
n, m = map(int, input().split())
a = [[INF]*n for _ in range(n)]
for i in range(m):
x, y = map(int, input().split())
a[x-1][y-1] = 1
a[y-1][x-1] = 1
for k in range(n):
for i in range(n):
for j in range(n):
if i == j:
a[i][j] = 0
else:
a[i][j] = min(a[i][j], a[i][k] + a[k][j])
ans = []
for i in a:
ans.append(sum(i))
for i in range(n):
if ans[i] == min(ans):
print(i+1)
break
'백준' 카테고리의 다른 글
백준 3055 탈출 (파이썬) (0) | 2020.02.16 |
---|---|
백준 2589 보물섬 (파이썬) (4) | 2020.02.16 |
백준 2206 벽 부수고 이동하기 (파이썬) (2) | 2020.02.16 |
백준 2644 촌수계산 (파이썬) (0) | 2020.02.16 |
백준 13460 구슬 탈출 2 (파이썬) (3) | 2020.02.16 |
Comments