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

초고

import sys
def build_graph(connections):
    graph = {}
    for node1, node2 in connections:
        if node1 not in graph:
            graph[node1] = [node2]
        else:
            graph[node1].append(node2)

        if node2 not in graph:
            graph[node2] = [node1]
        else:
            graph[node2].append(node1)
    return graph

def dfs(visited, graph, node):
    if node not in visited:
        visited.add(node)
        for neighbour in graph[node]:
            dfs(visited, graph, neighbour)


connections = []
c = int(sys.stdin.readline())
n = int(sys.stdin.readline())
for _ in range(n):
    node1, node2 = map(int,sys.stdin.readline().split())
    connections.append((node1,node2))

graph = build_graph(connections)
visited = set()

dfs(visited, graph, 1)
print(len(visited)-1)

• 정답은 맞았지만 connections 에 담지 않고 바로 graph 를 만드는 생각을 못했다..

개선된 코드

import sys
def dfs(visited, graph, node):
    if node not in visited:
        visited.add(node)
        for neighbour in graph[node]:
            dfs(visited, graph, neighbour)

n = int(sys.stdin.readline()) # 노드의 개수
m = int(sys.stdin.readline()) # 간선의 개수

graph = [ [] for _ in range(n+1)]
for _ in range(m):
    node1, node2 = map(int,sys.stdin.readline().split())
    graph[node1].append(node2)
    graph[node2].append(node1)

visited = set()

dfs(visited, graph, 1)
print(len(visited)-1)

• 입력을 받으면서 바로 graph를 만든다.

시간 복잡도

시간 복잡도는 O(V + E)

• V는 정점(컴퓨터)의 수이고 E는 간선(연결) 수

• 이는 DFS 알고리즘이 각 정점과 각 가장자리를 정확히 한 번만 방문하기 때문

• 집합을 사용하여 수행되는 노드 방문 여부 확인은 O(1)의 시간 복잡도.