문제

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

입력

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

출력

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

예제 입력 1

6 5 
1 2 
2 5 
5 1 
3 4 
4 6

예제 출력 1

2

 


 

DFS를 이용한 풀이 (python)

#백준 11724 DFS
import sys
sys.setrecursionlimit(10000)

def dfs(start):
    if(visited[start]):
        return
    visited[start] = True
    for node in adj[start]:
        if not visited[node]:
            dfs(node)


N,M=map(int,input().split(' '))
adj = [ [] for _ in range(N+1)]
visited = [False] * (N+1)
cnt = 0

for _ in range(M):
    x, y = map(int, input().split(' '))
    adj[x].append(y)
    adj[y].append(x)


for node in range(1, N+1):
    if not visited[node]:
        dfs(node)
        cnt +=1


print(cnt)

 


 

BFS를 이용한 풀이 (python)

 

#백준 11724 BFS
from collections import deque

def bfs(start):
    visited[start] = True
    queue.append(start)
    while queue:
        x=queue.popleft()
        for i in range(len(adj[x])):
            y=adj[x][i]
            if not visited[y]:
                visited[y] = True
                queue.append(y)


N,M=map(int,input().split(' '))
adj = [ [] for _ in range(N+1)]
visited = [False] * (N+1)
queue = deque()
cnt = 0

for _ in range(M):
    x, y = map(int, input().split(' '))
    adj[x].append(y)
    adj[y].append(x)


for node in range(1,N+1):
    if not visited[node]:
        bfs(node)
        cnt+=1

print(cnt)

 

대부분 DFS를 통해 구현하던데, 그 이유는 알겠다. BFS로 구현하는게 더 귀찮더라...ㅎㅎ

DFS(Depth First Search, 깊이 우선 탐색)은 그래프를 방문하거나 탐색하는 방법 중 하나이다. DFS는 주로 완전 탐색이나 백트래킹과 같이 탐색의 횟수, 즉 그래프의 최대 경로가 정해져 있거나 예측 가능한 경우에 이용한다. 

 

DFS는 선택한 정점을 저장하기 위한 도구로 큐 대신 스택을 이용한다는 점에서 BFS와 차이를 보인다. 다만 스택을 직접 사용하지 않고, 그 원리를 이용하는 재귀 함수를 통해 구현하는 편이다.

 

def dfs(start):
	if(visited[start]): 
    	return
    visited[start] = True
    for node in adj[start]:
        if not visited[node]:
            dfs(node)


N,M=map(int,input().split(' '))
adj = [ [] for _ in range(N+1)]
visited = [False] * (N+1)
start_node = input('시작 노드를 입력하세요 : ')

for _ in range(M):
    x, y = map(int, input().split(' '))
    adj[x].append(y)
    adj[y].append(x)


dfs(start_node)

다음 코드는 백준 11724번 풀이에서 가져와 약간 변형한 코드이다. 다만 보통 재귀 함수를 사용하는 경우 런타임 에러가 나는 경우가 잦아 다음의 코드를 통해 그 횟수를 직접 지정해주는 경우가 많다. 

 

import sys
sys.setrecursionlimit(10000)

BFS(Breadth First Search, 너비우선 탐색)은 그래프를 방문하거나 탐색하는 방법 중 하나이다. BFS를 이용하여 최단거리, 최소비용과 같이 최솟값과 관련된 문제를 해결할 수 있는데, 이때 그래프의 가중치(시간, 비용, 거리 등)가 1이어야만 한다. DFS는 그래프의 최대 경로(최대 깊이)가 예측할 수 있는 유한한 범위여야만 사용할 수 있지만, BFS는 모든 경로에 대한 동시 탐색이 가능하며 최대 경로를 몰라도 사용할 수 있다. 

 

from collections import deque

def bfs(start):
    visited[start] = True
    queue.append(start)
    while queue:
        x=queue.popleft()
        for i in range(len(adj[x])):
            y=adj[x][i]
            if not visited[y]:
                visited[y] = True
                queue.append(y)

#N:정점개수 M:간선개수
N,M=map(int,input().split(' '))
adj = [ [] for _ in range(N+1)]
visited = [False] * (N+1)
queue = deque()
start_node = input('검색을 시작할 노드를 입력하세요 : ')

for _ in range(M):
    x, y = map(int, input().split(' '))
    adj[x].append(y)
    adj[y].append(x)

bfs(start_node)

백준 11724번 코드 중 일부를 가져와 수정했다. 해당 코드는 정점, 간선의 개수를 입력받고 사용자에게 직접 어떤 정점이 연결되어 있는지 입력받는다.

 

BFS의 경우 를 사용하는 경우가 대부분이다. 방문했던 노드를 체크해야 살펴볼 노드를 큐에 넣을 때 중복이 발생하지 않기 때문이다.

 

python에서는 큐를 list 타입으로 사용하는 경우가 많은데, 살펴본 노드를 제거할 때, list.pop() 함수를 사용하는 경우 시간 복잡도가 O(N)이라 시간 복잡도 면으로 매우 비효율적이다.

 

따라서 collections 라이브러리의 deque을 사용하여 시간을 절약하는 편이 좋다. deque는 양 끝에서 접근이 가능하며, append(), extend(), pop(), popleft() 등의 함수를 통해 자료를 넣고 뺄 수 있다. 

+ Recent posts