[BOJ] 11724번 - 연결 요소의 개수

문제

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

11724번: 연결 요소의 개수

 

🚦 문제 유형

• 그래프 탐색
• bfs, dfs

 

✅ 문제 설명

• 방향이 없는 그래프가 주어졌을 때 연결 요소(Connected Component)의 개수를 구해야 합니다.
• 정점과 간선의 정보를 얻을 수 있고, 그래프에서 연결된 요소에 대한 정보로 양 끝점인 (u, v)가 주어집니다.
• (u, v)가 주어지면, (u, v)는 간선으로 연결된 것을 나타냅니다.
• 모든 간선의 정보가 주어졌을 때 그래프의 '연결 요소' 개수를 출력하는 것입니다.
• 연결 요소란?
  • 그래프에서 서로 연결된 요소인데, 서로 연결되어 있는 일종의 그룹을 말합니다.

 

✏️ Solution

그래프에서 정점을 돌아다니면서 서로 연결되어 있는지 확인하면 '연결 요소'를 찾을 수 있습니다.

bfs 또는 dfs를 사용해서 서로 연결되어 있는지를 확인하면 '연결 요소'의 개수를 count +1 하는 방식으로 코드를 구현합니다.

 

먼저, 그래프 탐색 전에 필요한 정보를 변수에 담는다.

import sys
input = sys.stdin.readline

N, M = map(int, input().split())    # N:정점개수, M:간선개수

 

그리고 다음 줄 부터 간선의 정보가 나오는데 정점 a에 정점 b가 연결되어 있음을 리스트에 담아봅니다.

# [[],[2,5],[1,5],[4], [3,6],[2,1],[4]] # 인덱스-연결된 정점을 담은 리스트.

graph = [[] for _ in range(N+1)]  # N+1 만큼의 리스트를 만든다.

for _ in range(M):
    u, v = map(int, input().split())    # 양 끝점 u, v 정보를 받는다.
    graph[u].append(v)  # 각 정점에 어떤 정점이 연결되어 있는지 graph에 정보 추가한다.
    graph[v].append(u)  # 서로 연결되어 있으니 반대쪽도 추가한다.

 

이제 생성된 그래프 변수 graph를 탐색하면 된다.

먼저 DFS 풀이이다.

 

1. DFS 풀이 방법

DFS는 스택을 사용해서 재귀함수를 구현하면 편리하다.

스택의 최상단 노드에 방문하지 않은 인접노드가 있으면 그 인접노드를 스택에 넣고 방문처리를 진행하는데 이 때 필요한 변수가 visited 이다.

그래프를 탐색하면서 방문할 예정인 노드가 방문 했는지 아닌지를 visited 변수로 참고할 수 있다.

dfs도 마찬가지로 풀이 방법의 큰 틀은 벗어나지 않는 것 같다.

def dfs(탐색할 그래프, 탐색 시작 노드):
	# 현재 방문한 노드를 방문처리한다.
    
    # 현재 노드에 연결된(인접한) 노드에 대해서,
    # 방문하지 않은 노드라면?
    # 다시 dfs를 시작한다. (재귀)

 

따라서 dfs 함수가 구현되면,

그래프의 1~N번 노드까지 하나씩 돌면서 방문여부에 따른 Dfs 탐색을 진행하고,

dfs 탐색이 끝났다면 연결된 요소를 모두 탐색한 것이므로 count+1을 해준다.

visited = [0]* (N+1)    # 정점의 개수 + 1 만큼 방문 리스트를 만든다.

cnt = 0

def dfs(graph, start):
    
    visited[start] = 1  # 해당 노드를 방문처리한다.
    
    for i in graph[start]: # 연결된 노드를 모두 방문하기 위해서,
        if visited[i] != 1: #방문하지 않은 노드라면,
            dfs(graph, i)   # 깊이 탐색을 시작한다.

# 1~N번 노드까지 돌면서 확인한다.
for i in range(1, N+1):
    if visited[i] != 1: # 해당 노드를 방문하지 않았다면,
        if not graph[i]:    # 해당 정점에 연결된 다른 정점이 없다면,
            cnt += 1    # 카운트 +1
            visited[i] = 1  # 해당 노드 방문 처리.
        else:   # 해당 정점에 연결된 다른 정점이 있다면,
            dfs(graph, i)   # Dfs 탐색
            cnt += 1    # 카운트 + 1
        dfs(graph, i)

print(cnt)

 

최종 코드는 다음과 같다.

# 연결 요소는 무엇일까?
# 연결 요소는 그래프에서 연결된 그룹의 개수 같다.

import sys
sys.setrecursionlimit(5000)
input = sys.stdin.readline

N, M = map(int, input().split())    # N:정점개수, M:간선개수

# [[],[2,5],[1,5],[4], [3,6],[2,1],[4]] # 인덱스-연결된 정점을 담은 리스트.

graph = [[] for _ in range(N+1)]  # N+1 만큼의 리스트를 만든다.
visited = [0]* (N+1)    # 정점의 개수 + 1 만큼 방문 리스트를 만든다.

for _ in range(M):
    u, v = map(int, input().split())    # 양 끝점 u, v 정보를 받는다.
    graph[u].append(v)  # 각 정점에 어떤 정점이 연결되어 있는지 graph에 정보 추가한다.
    graph[v].append(u)  # 서로 연결되어 있으니 반대쪽도 추가한다.
    
cnt = 0

def dfs(graph, start):
    
    visited[start] = 1  # 해당 노드를 방문처리한다.
    
    for i in graph[start]: # 연결된 노드를 모두 방문하기 위해서,
        if visited[i] != 1: #방문하지 않은 노드라면,
            dfs(graph, i)   # 깊이 탐색을 시작한다.

# 1~N번 노드까지 돌면서 확인한다.
for i in range(1, N+1):
    if visited[i] != 1: # 해당 노드를 방문하지 않았다면,
        if not graph[i]:    # 해당 정점에 연결된 다른 정점이 없다면,
            cnt += 1    # 카운트 +1
            visited[i] = 1  # 해당 노드 방문 처리.
        else:   # 해당 정점에 연결된 다른 정점이 있다면,
            dfs(graph, i)   # Dfs 탐색
            cnt += 1    # 카운트 + 1
        dfs(graph, i)

print(cnt)

 

2. BFS 풀이 방법

다음에 포스팅.

 

⚙️ Review

• dfs로 접근하는 것은 잘했다. 하지만 dfs를 완벽하게 구현하진 못했다.
  • dfs탐색을 위해 필요한 변수인 방문노드, 그래프 생성은 구현했지만 재귀 함수를 작성할 때 다음의 것들이 헷갈렸다.
    • return을 써줘야 하는지
    • count를 재귀함수 안에서 해야하는지, 아니면 함수 바깥에서 해야하는지
  • 뭔가 잘 풀리는 듯 하면서 한번에 풀 지는 못했다. 조금 더 연습이 필요하다.