|
import sys
input = sys.stdin.readline
Vn, En = map(int, input().split())
V = {}
for i in range(1, Vn + 1) :
V[i] = []
for i in range(En) :
v1, v2 = map(int, input().split())
V[v1].append(v2)
V[v2].append(v1)
gone = []
count = 0
def BFS(now) :
que = [now]
while que :
q = que[0]
gone.append(q)
del que[0]
for i in V[q] :
if not i in gone and not i in que :
que.append(i)
for i in range(1, Vn + 1) :
if not i in gone :
count = count + 1
BFS(i)
print(count)
|
입력받은 선의 정보대로 점의 연결관계를 기록한다.
함수의 실행점과 연결된 모든 점을 gone에 넣는 BFS를 정의한다.
모든 점에 for문을 돌면서 아직 gone에 들어가지 않았다면 BFS를 실행하면서 count +1
1주차의 안전 영역 문제와 같다.
'Week 01 ~ 04 : 알고리즘 문제 풀이' 카테고리의 다른 글
| 파이썬 백준 2718 미로 탐색 (0) | 2021.11.20 |
|---|---|
| 파이썬 백준 2606 바이러스 (0) | 2021.11.20 |
| 파이썬 백준 1260 DFS와 BFS (0) | 2021.11.19 |
| 파이썬 백준 1197 최소 스패닝 트리 (0) | 2021.11.19 |
| 파이썬 백준 5639 이진 검색 트리 (0) | 2021.11.19 |