[백준][11724] 연결 요소의 개수

• Problem Link : https://www.acmicpc.net/problem/11724

문제

• 방향 없는 그래프가 주어졌을 때, 연결 요소의 개수를 구하라.

입력

• 정점의 개수 N, 간선의 개수 M
• 둘째 줄부터 M개의 줄 : 양 끝점 u와 v

출력

• 연결 요소의 개수를 출력

풀이

DFS 방식을 이용해 문제를 해결

1. 방문하지 않은 노드가 있다면 count를 1 증가시키고 해당 노드를 시작 노드로 해서 DFS 방식을 이용한다.
2. DFS로 모든 노드를 방문하고 종료되면 또 다시 방문하지 않은 노드를 확인한다.
3. 방문하지 않은 노드가 있다면 다시 1-2번 과정을 반복한다. 
4. 방문하지 않은 노드가 없다면 모든 노드를 한 번씩은 방문했다는 뜻이므로 count를 출력한다.

DFS

def dfs(graph, v, visited):
    visited[v] = True
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)
    return

BFS 방식을 이용해서 문제를 해결

1. 방문하지 않은 노드가 있다면 count를 1 증가시키고 해당 노드를 시작 노드로 해서 BFS 방식을 이용한다.
2. BFS로 모든 노드를 방문하고 종료되면 또 다시 방문하지 않은 노드를 확인한다.
3. 방문하지 않은 노드가 있다면 다시 1-2번 과정을 반복한다. 
4. 방문하지 않은 노드가 없다면 모든 노드를 한 번씩은 방문했다는 뜻이므로 count를 출력한다.

BFS

from collections import deque

def bfs(graph, start, visited):
    queue = deque([start])
    visited[start] = True

    while queue:
        v = queue.popleft()
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

오류 및 해결

하지만 DFS를 이용한 실행 중 시간 초과가 발생했다. 왜 시간초과가 발생하는지 구글링을 해봤는데, 알고보니 입력받는 방법이 input()과 sys.stdin.readline() 두 가지 방식이 있는데 input()의 실행이 굉장히 느리다는 것을 알게되어서 다음과 같은 문구를 코드 맨 위에 추가로 작성해주었다.

input = sys.stdin.readline

input과 sys.stdin.readline의 차이점

• input()
  - input() 내장 함수는 parameter로 prompt message를 받을 수 있다. 따라서 입력받기 전 prompt message를 출력해야 한다. 물론 prompt message가 없는 경우도 있지만, 이 경우에도 약간의 부하로 작용할 수 있다.
  - input() 내장 함수는 입력받은 값의 개행 문자를 삭제시켜서 리턴한다. 즉, 입력받은 문자열에 rstrip() 함수를 적용시켜 리턴한다.

• sys.stdin.readline()
  - sys.stdin.readline()은 prompt message를 인수로 받지 않는다.
  - sys.stdin.readline()은 개행문자를 포함한 값을 리턴한다.

• 결론
  input() 내장함수는 sys.stdin.readline()과 비교해서 prompt message를 출력하고, 개행 문자를 삭제한 값을 리턴시키기 때문에 굉장히 느리다.

  sys.stdin.readline()를 활용해서 입력을 받는 것이 실행 시간 측면에서는 유리하다.

코드

import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.readline

from collections import deque


def bfs(graph, start, visited):
    queue = deque([start])
    visited[start] = True

    while queue:
        v = queue.popleft()
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True


def dfs(graph, v, visited):
    visited[v] = True
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)
    return


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

cnt = 0
visited = [False] * (n + 1)
for i in range(1, n + 1):
    if not visited[i]:
        bfs(graph, i, visited)
        cnt += 1

print(cnt)