๋ฌธ์ ๋ณด๋ฌ๊ฐ๊ธฐ
๐ต๏ธโ๏ธ ๋ฌธ์
์ ์ข ๋ฐ์ด๋ฌ์ค์ธ ์ ๋ฐ์ด๋ฌ์ค๋ ๋คํธ์ํฌ๋ฅผ ํตํด ์ ํ๋๋ค. ํ ์ปดํจํฐ๊ฐ ์ ๋ฐ์ด๋ฌ์ค์ ๊ฑธ๋ฆฌ๋ฉด ๊ทธ ์ปดํจํฐ์ ๋คํธ์ํฌ ์์์ ์ฐ๊ฒฐ๋์ด ์๋ ๋ชจ๋ ์ปดํจํฐ๋ ์ ๋ฐ์ด๋ฌ์ค์ ๊ฑธ๋ฆฌ๊ฒ ๋๋ค.
์๋ฅผ ๋ค์ด 7๋์ ์ปดํจํฐ๊ฐ <๊ทธ๋ฆผ 1>๊ณผ ๊ฐ์ด ๋คํธ์ํฌ ์์์ ์ฐ๊ฒฐ๋์ด ์๋ค๊ณ ํ์. 1๋ฒ ์ปดํจํฐ๊ฐ ์ ๋ฐ์ด๋ฌ์ค์ ๊ฑธ๋ฆฌ๋ฉด ์ ๋ฐ์ด๋ฌ์ค๋ 2๋ฒ๊ณผ 5๋ฒ ์ปดํจํฐ๋ฅผ ๊ฑฐ์ณ 3๋ฒ๊ณผ 6๋ฒ ์ปดํจํฐ๊น์ง ์ ํ๋์ด 2, 3, 5, 6 ๋ค ๋์ ์ปดํจํฐ๋ ์ ๋ฐ์ด๋ฌ์ค์ ๊ฑธ๋ฆฌ๊ฒ ๋๋ค. ํ์ง๋ง 4๋ฒ๊ณผ 7๋ฒ ์ปดํจํฐ๋ 1๋ฒ ์ปดํจํฐ์ ๋คํธ์ํฌ์์์ ์ฐ๊ฒฐ๋์ด ์์ง ์๊ธฐ ๋๋ฌธ์ ์ํฅ์ ๋ฐ์ง ์๋๋ค.
์ด๋ ๋ 1๋ฒ ์ปดํจํฐ๊ฐ ์ ๋ฐ์ด๋ฌ์ค์ ๊ฑธ๋ ธ๋ค. ์ปดํจํฐ์ ์์ ๋คํธ์ํฌ ์์์ ์๋ก ์ฐ๊ฒฐ๋์ด ์๋ ์ ๋ณด๊ฐ ์ฃผ์ด์ง ๋, 1๋ฒ ์ปดํจํฐ๋ฅผ ํตํด ์ ๋ฐ์ด๋ฌ์ค์ ๊ฑธ๋ฆฌ๊ฒ ๋๋ ์ปดํจํฐ์ ์๋ฅผ ์ถ๋ ฅํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
๐ก ์ ๋ ฅ
์ฒซ์งธ ์ค์๋ ์ปดํจํฐ์ ์๊ฐ ์ฃผ์ด์ง๋ค. ์ปดํจํฐ์ ์๋ 100 ์ดํ์ด๊ณ ๊ฐ ์ปดํจํฐ์๋ 1๋ฒ ๋ถํฐ ์ฐจ๋ก๋๋ก ๋ฒํธ๊ฐ ๋งค๊ฒจ์ง๋ค. ๋์งธ ์ค์๋ ๋คํธ์ํฌ ์์์ ์ง์ ์ฐ๊ฒฐ๋์ด ์๋ ์ปดํจํฐ ์์ ์๊ฐ ์ฃผ์ด์ง๋ค. ์ด์ด์ ๊ทธ ์๋งํผ ํ ์ค์ ํ ์์ฉ ๋คํธ์ํฌ ์์์ ์ง์ ์ฐ๊ฒฐ๋์ด ์๋ ์ปดํจํฐ์ ๋ฒํธ ์์ด ์ฃผ์ด์ง๋ค.
๐ ์ถ๋ ฅ
1๋ฒ ์ปดํจํฐ๊ฐ ์ ๋ฐ์ด๋ฌ์ค์ ๊ฑธ๋ ธ์ ๋, 1๋ฒ ์ปดํจํฐ๋ฅผ ํตํด ์ ๋ฐ์ด๋ฌ์ค์ ๊ฑธ๋ฆฌ๊ฒ ๋๋ ์ปดํจํฐ์ ์๋ฅผ ์ฒซ์งธ ์ค์ ์ถ๋ ฅํ๋ค.
๐โ๏ธ ํ์ด๋ณด์~
com = int(input())
cnt = 0
adj = [[] for _ in range(com+1)]
visited = [False] * (com+1)
for i in range(int(input())):
x, y = map(int, input().split())
adj[x].append(y)
adj[y].append(x)
def dfs(v):
visited[v] = True
for e in adj[v]:
if not visited[e]:
dfs(e)
dfs(1)
for i in range(len(visited)):
if visited[i] == True:
cnt += 1
print(cnt-1)
2. BFS๋ก ํ์ด๋ณด๋ฉด,,,
from collections import deque
com = int(input())
cnt = 0
adj = [[] for _ in range(com+1)]
visited = [False] * (com+1)
for i in range(int(input())):
x, y = map(int, input().split())
adj[x].append(y)
adj[y].append(x)
def bfs(v):
q = deque([v])
visited[v] = True
while q:
v = q.popleft()
for e in adj[v]:
if not visited[e]:
q.append(e)
visited[e]= True
bfs(1)
for i in range(len(visited)):
if visited[i] == True:
cnt += 1
print(cnt-1)
'๐ต๏ธโโ๏ธ > BOJ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Python] BOJ 1325 ํจ์จ์ ์ธ ํดํน (BFS) (1) | 2021.11.19 |
---|---|
[Python] BOJ 1012 ์ ๊ธฐ๋ ๋ฐฐ์ถ (DFS/BFS) (0) | 2021.11.18 |
์ฝํ ๋๋น ๋ฐฑ์ค๋ฌธ์ ์ถ์ฒ (0) | 2021.11.05 |
[Python] BOJ 14719 ๋น๋ฌผ (0) | 2021.11.04 |
[Python] BOJ 1149 RGB๊ฑฐ๋ฆฌ (dp) (0) | 2021.11.04 |