[알고리즘] 백준 11724 연결 요소의 개수 (파이썬 풀이)

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

11724번: 연결 요소의 개수

해결코드

import sys
sys.setrecursionlimit(10000)

input = sys.stdin.readline

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

for _ in range(m):
    u,v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

def dfs(n):
    visited[n] = 1
    for i in graph[n]:
        if visited[i] == 0:
            dfs(i)
            
result = 0
for i in range(1, n+1):
    if visited[i]==0:
        dfs(i)
        result +=1
        
print(result)

문제풀이

전형적으로 dfs를 이용하여 푸는 문제이다.

문제 푸는 원리는 dfs를 이용하여

방문하지않은 한 요소에 방문했을 때 연결되어 있는 모든 요소를 방문처리 하고

다음요소로 넘어가서 같은 방식으로 처리하는 방식이다.

 

코드를 보자

 

n,m = map(int, input().split())

일단 n,m에 각각 정점의 개수와 간선의 개수를 받아준다.

 

graph = [[]*(n+1) for _ in range(n+1)]
visited = [0]*(n+1)

그래프를 저장하는 리스트 graph와 방문리스트 visted를 선언한다.

 

for _ in range(m):
    u,v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

m개만큼 for문을 실행한다.

간선의 양 끝점 u,v를 입력받아준다.

그리고 graph리스트에 연결요소들을 추가시켜준다.

ex) 예제 입력 1 일 때

graph = [[], [2, 5], [1, 5], [4], [3, 6], [2, 1], [4]]

          정점   1      2     3     4      5      6  과 연결된 정점들

 

result = 0
for i in range(1, n+1):
    if visited[i]==0:
        dfs(i)
        result +=1

연결 요소 개수를 나타내는 result값을 0으로 선언한다.

1부터n까지 범위로 for문을 실행시킨다.

만약 visited[i]가 0이라면(방문하지 않았다면)

dfs(i) 함수를 실행시킨다.

실행시키고 result값에 1 더해준다.

 

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

dfs함수를 실행시키면

i -> n으로 넘어와서 visited[n]을 1로 바꾼다.(방문 처리한다)

그리고 graph[n]의 원소로 for문을 실행시킨다.(n과 연결되어 있는 다른 정점들의 방문처리 목적)

만약 visited[i]가 방문하지 않은 상태라면

dfs(i)를 또 실행한다. (연결된 모든 정점들을 방문)

 

print(result)

result값을 출력한다