Jin의 일상

두 가지 다른 리스트 구조로 풀었습니다. 그랬더니 25% 더 빨라졌습니다. 메모리는 42% 개선됐구요.
같은 코드더라도 답을 제출할 때 마다 시간 효율이 다르게 측정되긴 하지만 꽤 큰 차이라서 기록합니다!

아래와 같이 노드가 주어졌다고 가정해보겠습니다.

A 코드는 그래프에 값을 담을 때 연결된 정점만 담습니다.
[[1, 4],
[0, 4, 3, 2],
[3, 1],
[2, 5, 4, 1],
[1, 0, 3],
[3]]

B 코드는 모든 노드와의 연결을 1(연결 됐음)과 0(안됐음)으로 표현합니다.
[[0, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 1, 0],
[0, 1, 0, 1, 1, 1, 0],
[0, 0, 1, 0, 1, 0, 0],
[0, 0, 1, 1, 0, 1, 1],
[0, 1, 1, 0, 1, 0, 0],
[0, 0, 0, 0, 1, 0, 0]]


현재까지 알아낸 바로는 리스트에 append할 때 더 많은 런타임이 발생합니다.
A와 B 코드의 입력 방식에 따른 런타임 시간을 비교한 코드입니다.

import time
R = 10000000


# A 코드 : 연결된 정점만 담음.
c = time.time()
t2 = []
for i in range(R):
    t2.append(i)
d = time.time()
assert d - c == 1.2  # 물론 항상 다름^^


# B 코드 : 각 노드의 연결 여부를 0과 1로 표현
a = time.time()
t1 = [0] * R
for i in range(R):
    t1[i] = i
b = time.time()
assert b - a == 0.64  # 물론 항상 다름^^

A 코드

# A 코드: 메모리 63920 KB, 시간 728 ms
import sys
sys.setrecursionlimit(10000)
INPUT = sys.stdin.readline


def dfs(graph, visited, n):
    visited[n] = 1
    for i in graph[n]:
        if visited[i] == 0:
            dfs(graph, visited, i)


def solution():
    vertex_num, edges_num = map(int, INPUT().split())

    graph = [[] for _ in range(vertex_num)]
    for _ in range(edges_num):
        a, b = map(int, INPUT().split())
        graph[a - 1].append(b - 1)
        graph[b - 1].append(a - 1)

    cnt = 0
    visited = [0] * vertex_num
    for i in range(vertex_num):
        if visited[i] == 0:
            cnt += 1
            dfs(graph, visited, i)
    return cnt

print(solution())

B 코드

# D 코드: 메모리 37012KB, 시간 552ms
import sys
sys.setrecursionlimit(10000)
sys.stdin = open('input.txt', 'r')

INPUT = sys.stdin.readline


def dfs(i, graph, visited, vertex_num):
    visited[i] = True
    for j in range(1, vertex_num + 1):
        if visited[j]:
            continue
        if graph[i][j] == 0:
            continue
        dfs(j, graph, visited, vertex_num)


def solution():
    vertex_num, edges_num = map(int, INPUT().split())
    graph = [[0] * (vertex_num + 1) for i in range((vertex_num + 1))]
    visited = [0] * (vertex_num + 1)

    for i in range(edges_num):
        a, b = map(int, INPUT().split())
        graph[a][b] = 1
        graph[b][a] = 1

    cnt = 0
    for i in range(1, vertex_num + 1):
        if visited[i] == 0:
            cnt += 1
            dfs(i, graph, visited, vertex_num)
    return cnt
print(solution())