[백준] 11724 : 연결 요소의 개수 - Python

문제

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

입력

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

출력

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

import sys
sys.stdin = open("input.text", "rt")
sys.setrecursionlimit(10000)
input = sys.stdin.readline

n, m = map(int, input().split())
g = [[] for _ in range(n+1)]   #빈 리스트로 했어야함..! 무방향 노드들만 있는 상태니까! 
ch = [0] * (n+1)
## 그래프 전체 0으로 채워야 하는 것을 상하좌우 구분 있을 경우고 그 외에는 이런 식으로 빈 리스트에 추가하는 식으로 진행하자.
for _ in range(m):
    u, v = map(int, input().split())
    g[u].append(v)
    g[v].append(u)

cnt = 0
def DFS(v):
    ch[v] = 1 #방문 표시
    for x in g[v]: #인접노드들
        if ch[x] == 0:
            DFS(x)
    
for i in range(1,n+1):
    if ch[i] == 0: #방문 전
        DFS(i)
        cnt += 1

print(cnt)


        

⚽ 코멘트

• 입력예시를 통해 인접 리스트로 할지 인접행렬로 할지를 정하면 된다.
• 또한 dfs 한번이면 연결요소 하나를 찾는 것으로 생각하고 코드를 짰어야 했다.

이 문제의 경우 연결요소를 찾는 문제인데 DFS로 해결하기 쉽다.
연결 요소란 그래프의 개수를 생각하면 된다. 정점 사이에 겹쳐진 것이 없고 나누어진 그래프를 연결 요소라고 생각하면 된다. 연결 요소를 구하는 것은 DFS나 BFS를 이용할 것.

이 문제의 경우 그래프 2차원 리스트에 연결된 정보를 입력할 것인데 정점 개수만큼 0을 먼저 세팅해줄 필요가 없다. 다른 문제들처럼 상하좌우를 파악하는 것이 아닌 딱 인접 노드들만 알면되기 때문에 입력할 때 append로 추가해주는게 시간 복잡도 측면에서 굿.

• 역시 이 문제도 방문 표시를 해야하기에 체크 리스트 하나가 더 필요하다. 이미 방문한 노드는 더이상 방문하지 않아야 연결 요소를 찾을 수 있다.

dfs, bfs 다시 풀어봄

• dfs

n,m = map(int, input().split())
g = [[] for _ in range(n+1)] # 1번 인덱스부터 사용

for _ in range(m):
    a,b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)

ch = [0] * (n+1)
def dfs(v):
    ch[v] = 1  #방문처리

    for node in g[v]: # 현재 노드의 인접 노드들
        if ch[node] == 0: #방문 전
            ch[node] = 1 # 방문처리 후 들어감
            dfs(node)
cnt = 0
for i in range(1,n+1):
    if ch[i] == 0:
        dfs(i)
        cnt += 1
print(cnt)

• bfs
  ``python
  import sys
  sys.stdin = open("input.txt", "rt")
  from collections import deque

n,m = map(int, input().split())
g = [[] for _ in range(n+1)] # 1번 인덱스부터 사용

for _ in range(m):
a,b = map(int, input().split())
g[a].append(b)
g[b].append(a)

ch = [0] * (n+1)
def bfs(v):
ch[v] = 1 # 시작노드 방문처리
dq = deque()
dq.append(v)

while dq:
    now = dq.popleft()
    for node in g[now]: # 현재 노드의 인접노드들
        if ch[node] == 0: #아직 방문 전
            ch[node] = 1 # 방문 처리 후
            dq.append(node)

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