[백준] 11724번 연결 요소의 개수 - (Python)

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

11724번: 연결 요소의 개수

 

이 문제는 전형적인 그래프이론 문제로, DFS, BFS를 이용하여 문제를 해결할 수 있습니다.

연결 노드들의 간선을 따라 이동한 뒤, DFS나 BFS 함수를 빠져나온 횟수를 카운팅 하면 됩니다.

※ 고려사항

1. 입출력을 어떻게 받을것인가?

2. DFS나 BFS 함수 구현

3. 함수 실행 처리

 

---

1. 입출력을 어떻게 받을것인가?

먼저 방문처리를 할 배열과 간선과 노드를 저장할 배열 2개를 생성 해줍니다.

간선과 노드를 저장하는 배열의 경우, 2차원 배열을 통해 해당 리스트에는 각 인덱스마다 연결되고 있는 노드를 삽입합니다.

노드 번호와 배열의 index 순서를 동일하게 하기위해, 노드의 크기 + 1 만큼의 배열크기를 할당합니다.

 

import sys
input = sys.stdin.readline

sys.setrecursionlimit(10000)

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

# 방문처리와 노드 입력받음
visited = [0] * (n+1)
graph = [[] for _ in range(n+1)]

# 연결요소
cnt = 0

# 연결노드는 1처리
for i in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

 

 

graph를 출력해보면 다음과 같습니다.

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

 

2. DFS나 BFS 함수 구현

해당문제를 푸는방법은 2가지가 있으며, 본인은 DFS를 이용해서 구현했습니다. DFS는 재귀와 Stack을 이용한 풀이가 있습니다. 재귀를 이용할 경우 RecursiveError가 발생할 수 있으므로, 가급적 stack 풀이를 지향하는 것이 좋다고 생각됩니다.

이해를 돕기위해 재귀와 stack구조 2가지 방법 모두를 설명하겠습니다.

(본인은 재귀로 이해를 한 뒤, stack을 이용하여 다시 품)

 

1. 재귀

# DFS 재귀
def dfs(v):

    # 방문처리
    visited[v] = 1

    # 연결노드에 방문하지 않았으면, 재귀
    for i in graph[v]:
        if visited[i] == 0:
            dfs(i)

 

2. Stack

# DFS Stack
def dfs_stack(v):

    # stack에 삽입
    stack = [v]

    # stack이 empty일때까지
    while stack:

        # 가장 최근 요소 pop
        v = stack.pop()

        # 방문하지 않았다면 방문처리하고 연결 노드 stack에 삽입
        if visited[v] == 0:
            visited[v] = 1
            for i in graph[v]:
                stack.append(i)

 

3. 함수 실행 처리

실행과 관련해서는 DFS가 인접 노드 모두를 방문하기 때문에 이미 방문한 노드들에 대해서는 count해서는 안됨으로 중복처리 되지 않게합니다.

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

 

---

전체코드

import sys
input = sys.stdin.readline

sys.setrecursionlimit(10000)

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

# 방문처리와 노드 입력받음
visited = [0] * (n+1)
graph = [[] for _ in range(n+1)]

# 연결요소
cnt = 0

# 연결노드는 1처리
for i in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

# DFS Stack
def dfs_stack(v):

    # stack에 삽입
    stack = [v]

    # stack이 empty일때까지
    while stack:

        # 가장 최근 요소 pop
        v = stack.pop()

        # 방문하지 않았다면 방문처리하고 연결 노드 stack에 삽입
        if visited[v] == 0:
            visited[v] = 1
            for i in graph[v]:
                stack.append(i)

# DFS 재귀
def dfs(v):

    # 방문처리
    visited[v] = 1

    # 연결노드에 방문하지 않았으면, 재귀
    for i in graph[v]:
        if visited[i] == 0:
            dfs(i)
    
# 방문하지 않은 노드만 cnt + 1    
for i in range(1, n+1):
    if visited[i] == 0:
        dfs_stack(i)
        cnt+=1
print(cnt)

---

아직 DFS, BFS를 이론적으로만 학습하여, 코드 구현이 다소 어려움이 있습니다. 입출력 처리를 어떻게 하느냐를 먼저 정하고 문제에 접근하는 것이 좋다고 생각이 됩니다. 문제마다 요구하는 부분이 제각각이기 때문에 다양한 문제를 통한 학습이 중요하다고 생각됩니다. 혹시, 풀이나 설명방식이 잘못된 부분이 있다면 언제든 피드백 해주시면 감사하겠습니다 ^~^