[백준] [파이썬] [Graph] [BFS] [DFS] 11724번: 연결 요소의 개수

문제 보러 가기

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (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

---

일단 '연결요소'가 무엇인지 알기 힘들었다. 그러나 입력 예제를 그림으로 그려보고 예제 출력을 보면 단번에 이해할 수 있다.

 

1번 예제 같은 경우, 직접 그래프를 그려보면 다음과 같은 모양으로 그려진다. 

125 / 34 형태로, 2개의 그래프이자 2개의 영역으로 나눠진 것으로 볼 수 있다.

 

다음으로 2번 예제의 경우, 직접 그래프를 그려보면 다음과 같은 모양으로 그려진다. 

123456이 모두 연결되어 1개의 그래프이자 1개의 영역으로 볼 수 있다.

를 통해 문제에서 말하는 연결 요소라는 것은 그래프의 개수 또는 영역의 개수로 이해하면 된다.

 

따라서, DFS 또는 BFS를 수행하는 횟수가 연결 요소의 개수이다.

1번 예시는 2번의 DFS/BFS를 통해 125 방문, 34 방문을 할 수 있고, 2번 예시는 1번의 DFS/BFS를 통해 123456을 모두 방문할 수 있다.

DFS/BFS가 한 번 끝날 때마다 count+1을 해주면 최종적으로 연결요소의 개수를 구할 수 있다.

---

BFS로 푼 코드

 

import sys 
from collections import deque

if __name__=="__main__":
    N,M=map(int, sys.stdin.readline().split())    # 정점의 개수:N, 간선의 개수:M 
    graph=[[] for _ in range(N+1)]
    visited=[0]*(N+1)
    for _ in range(M):
        u,v=map(int, sys.stdin.readline().split())
        graph[u].append(v)
        graph[v].append(u)
    
    Q=deque()
    cnt=0
    for i in range(1,N+1):          # 모든 정점을 살핌 
        if visited[i]==0:           # 첫 방문이면 
            Q.append(i)             # 큐에 정점 번호 넣기
            visited[i]=1            # 방문 체크 
            while Q:                # 하나의 노드에 연결된 모든 노드 살펴보기 -> 다 방문 체크해버리기
                v=Q.popleft()
                for e in graph[v]:
                    if visited[e]==0:
                        Q.append(e)
                        visited[e]=1
            cnt+=1
    print(cnt)

 

DFS로 푼 코드

 

import sys 

def DFS(v):
    visited[v]=1
    for e in graph[v]:
        if visited[e]==0:
            DFS(e)


if __name__=='__main__':
    n,m=map(int, input().split())
    graph=[[] for _ in range(n+1)]
    visited=[0]*(n+1)

    for i in range(m):
        u,v=map(int, input().split())
        graph[u].append(v)  # 방향성이 없는 그래프이기 때문에 graph[u][v]=1 이렇게 2차원 행렬을 하지 않는다.
        graph[v].append(u)     

    cnt=0
    for i in range(1,n+1):
        if visited[i]==0:
            DFS(i)
            cnt+=1
    print(cnt)

 

---