ํฐ์คํ ๋ฆฌ ๋ทฐ
algorithm/baekjoon
[๋ฐฑ์ค] 1389. ์ผ๋น ๋ฒ ์ด์ปจ์ 6๋จ๊ณ ๋ฒ์น / python ํ์ด์ฌ
jen jen 2021. 4. 8. 02:02728x90
๐ฉ ๊ทธ๋ํ์ด๋ก , ๊ทธ๋ํํ์, BFS
thinking
๋ฌธ์ ๋ฅผ ์ฝ์ด๋ณด๋ BFS์ฌ์ BFS๋ก ํ์๋ค.
์ธ์ ๋ฆฌ์คํธ๋ฅผ ๋ง๋ค์ด์ค ํ, 1๋ฒ๋ถํฐ ์ํํ๋ฉด์ ์ผ๋น๋ฒ ์ด์ปจ์๋ฅผ ์นด์ดํ ํ ํ ๋ฆฌ์คํธ์ ๋ฃ๊ณ
๊ทธ ๋ฆฌ์คํธ์์ ๊ฐ์ฅ ์์ ๊ฐ์ ์ธ๋ฑ์ค๋ฅผ ์ถ๋ ฅํ๋ค.
์ฝ๋
from collections import deque
def BFS(i):
visited = [0] * (N+1)
queue.append(i)
visited[i] = 1
while queue:
t = queue.popleft()
for v in edge_list[t]:
if not visited[v]:
visited[v] = visited[t]+1
queue.append(v)
return sum(visited)
N, M = map(int, input().split()) # N:์ ์ ์ ์, M: ์น๊ตฌ๊ด๊ณ ์
edge_list = [[] for _ in range(N+1)]
for _ in range(M):
s, e = map(int, input().split())
edge_list[s].append(e)
edge_list[e].append(s)
queue = deque()
res = []
for i in range(1, N+1):
res.append(BFS(i))
print(res.index(min(res))+1)
'algorithm > baekjoon' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[๋ฐฑ์ค] 1541. ์์ด๋ฒ๋ฆฐ ๊ดํธ / python ํ์ด์ฌ (0) | 2021.04.10 |
---|---|
[๋ฐฑ์ค] 1620. ๋๋์ผ ํฌ์ผ๋ชฌ ๋ง์คํฐ ์ด๋ค์ / python ํ์ด์ฌ (0) | 2021.04.10 |
[๋ฐฑ์ค] 1260. DFS์ BFS / python ํ์ด์ฌ (0) | 2021.04.08 |
[๋ฐฑ์ค] 1012. ์ ๊ธฐ๋ ๋ฐฐ์ถ / python ํ์ด์ฌ (0) | 2021.04.08 |
[๋ฐฑ์ค] 1003. ํผ๋ณด๋์น ํจ์ / python ํ์ด์ฌ (0) | 2021.04.08 |
๋๊ธ
๊ธ ๋ณด๊ดํจ
TAG
- 20056 ๋ง๋ฒ์ฌ ์์ด์ ํ์ด์ด๋ณผ
- swea
- ์ผ์ฑ๊ธฐ์ถ
- ์์ด๋๋ง์๊ธฐ
- 17406 ๋ฐฐ์ด๋๋ฆฌ๊ธฐ4
- ์ผ์ฑ์ฝํ
- ๋ฐฑ์ค
- merge์๋ฌ
- react
- 20057 ๋ง๋ฒ์ฌ ์์ด์ ํ ๋ค์ด๋
- dfs
- 2018 ์นด์นด์ค ๊ณต์ฑ
- 21609 ์์ด ์คํ๊ต
- git ๋ฏธ๋ฌ๋ง
- Python
- ํ๋ก๊ทธ๋๋จธ์ค
- merge ์๋ฌ
- ๊ธฐ์ง๊ตญ์ค์น
- 2579 ๊ณ๋จ์ค๋ฅด๊ธฐ
- ์๊ณ ๋ฆฌ์ฆ
- dp
- ๋ธ๋ฃจํธํฌ์ค
- BFS
- ํ์ด์ฌ
- ๋ณด์์ผํ
์ต๊ทผ์ ์ฌ๋ผ์จ ๊ธ
- Total
- Today
- Yesterday
์ต๊ทผ์ ๋ฌ๋ฆฐ ๋๊ธ