[python]백준 11724번: 연결 요소의 개수(그래프)

# 11724 연결 요소의 개수

https://www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

⭐ 코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

N, M = map(int, input().split())

graph = [[] for i in range(N+1)]
visited = [0] * (N+1)

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

def dfs(v):
    visited[v] = 1
    for i in graph[v]:
        if visited[i] == 0:
            visited[i] = 1
            dfs(i)

count = 0
for i in range(1, N+1):
    if visited[i] == 0:
        count += 1
        dfs(i)
print(count)

📝 풀이

https://velog.io/@kjh107704/%EA%B7%B8%EB%9E%98%ED%94%84-%EC%97%B0%EA%B2%B0-%EC%9A%94%EC%86%8C

연결 요소의 개수를 구하는 문제이다. 연결 요소는 위와 같이 나누어진 각각의 그래프를 연결 요소라고 한다. 즉 노란색 덩어리가 연결 요소 하나, 초록색 덩어리가 연결 요소 하나를 차지하므로 전체 연결 요소는 2개가 존재하는 셈이다. dfs를 돌면서 방문 여부를 체크해주고 dfs를 시작할때마다 count를 증가시켜주면 연결 요소의 갯수를 찾을 수 있다.

🔓 정답 코드 뜯어보기

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

N, M = map(int, input().split())

graph = [[] for i in range(N+1)]
visited = [0] * (N+1)

먼저, dfs를 사용하기 앞서서 재귀제한의 허용치를 넓혀주기 위해 sys.setrecursionlimit(10**7)를 해준다. 그리고 graph와 방문처리 할 visited를 생성시켜준다.

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

그리고 간선의 갯수 M만큼 반복문을 실행시켜주고, graph의 요소들을 연결시켜준다.

def dfs(v):
    visited[v] = 1
    for i in graph[v]:
        if visited[i] == 0:
            visited[i] = 1
            dfs(i)

count = 0
for i in range(1, N+1):
    if visited[i] == 0:
        count += 1
        dfs(i)
print(count)

dfs 함수를 생성해주고, 처음 들어온 값을 visited[v] = 1로 방문처리 해준다. 그래프를 순회하면서 방문하지 않은 곳이라면 방문처리를 해주고 dfs 재귀함수를 실행시켜준다.

 

1부터 정점의 갯수 + 1만큼 반복문을 실행시켜주면서 방문하지 않은 곳을 만날 때마다 count를 증가시켜주고 dfs를 실행시켜준다. 방문하지 않은 곳이 더이상 없다면 count를 출력시켜준다.