백준 11724 연결 요소의 개수 BFS 파이썬 풀이

연결 요소의 개수 성공

 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

3 초

512 MB

91149

41381

27304

42.369%

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

출력

첫째 줄에 연결 요소의 개수를 출력한다.

예제 입력 1 복사

6 5
1 2
2 5
5 1
3 4
4 6

예제 출력 1 복사

2

예제 입력 2 복사

6 8
1 2
2 5
5 1
3 4
4 6
5 4
2 4
2 3

예제 출력 2 복사

1

##연결요소의 개수를 출력하라 BFS
import sys
from collections import deque

input=sys.stdin.readline
n, m= map(int, input().split())

graph=[[]for i in range(n+1)]
for i in range (m):
    a, b=map(int, input().split())
    graph[a].append(b)
    graph[b].append(a) ##양방향 연결
    
def bfs(graph, a, v):
    queue=deque()
    queue.append(a)
    v[a]=True
    while queue:
        k=queue.popleft()
        for i in graph[k]: ##k의 안에있는 애들을 
            if v[i]==False:
                queue.append(i)
                v[i]=True
            
cnt=0      
    
visit=[False]*(n+1)
    
for i in range (1,n+1):
    if visit[i]==False: ##방문하지 않았다면 간다 
        bfs(graph, i, visit)
        cnt+=1
print(cnt)

분명 맞는데 시간초과가 뜬다면 

import sys

input=sys.stdin.readline을 쓰자 .. 

 

BFS는 너비 우선 탐색 알고리즘으로 큐를 사용한다 

연결된 덩어리를 찾아야하기에 각 노드를 도는데, 

visit리스트를 만들어 방문하지 않았다면 bfs함수를 실행하고, cnt를 추가한다

bfs함수에서는 큐에 노드를 넣고, 노드와 연결된 다른 노드를 큐에 차례차례 추가하고

큐가 빌 때까지 돌고 방문처리를 해 덩어리를 만든다