[1325] 효율적인 해킹 (백준)

출처:https://www.acmicpc.net/problem/1325

문제는 완전탐색 + 깊이 우선 탐색으로 해결했다. 시간 복잡도를 계산해보자. 각 노드에서 한번씩 탐색을 수행한 후 가장 많은 노드를 탐색한 시작점을 기록하는 것이다. 인접리스트로 이루어진 그래프를 깊이 우선 탐색하는 경우 V+E(노드의 개수 + 간선의 개수)이고, 여기서 V(노드의 개수, 완전 탐색)를 곱한게 시간복잡도를 나타낸다. 즉, 10,000*110,000 = 11억이다. 파이썬의 1초당 연산시간이 2000만번으로 알려져 있고(출처), 이는 대략 5초정도의 시간이 걸린다. 문제에서는 5초가 주어졌기 때문에 완전탐색으로도 풀 수 있는것이다. 

 

다음으로는 깊이 우선 탐색. 연산이 빠른 pypy3을 선택하여도 재귀적으로 구현하다보면 메모리를 많이 잡아먹기 때문에 메모리초과가 뜨는 것을 쉽게 볼 수 있다. 따라서 나는 스택으로 구현하였다. 시작 노드를 스택에 넣으면서 방문처리를 하고, 깊이 우선 탐색을 시작하면 스택에 노드가 존재하는 한 스택에서 하나씩 꺼내며 인접한 노드들 중에 방문하지 않은 노드를 체크하고 개수를 세는 방식이다. 코드를 확인해보자.

 

import sys
input = sys.stdin.readline
n, m = map(int, input().strip().split())
nodes = [[] for _ in range(n+1)]

for _ in range(m):
    a, b = map(int, input().split())
    nodes[b].append(a)
    
cnts = [0]*(n+1)
def dfs(cur):
    visit = [0]*(n+1)
    visit[cur] = 1
    cnt = 1
    stack = [cur]
    while stack:
        node = stack.pop()
        for nxt in nodes[node]:
            if not visit[nxt]:
                visit[nxt] = 1
                cnt += 1
                stack.append(nxt)
    return cnt

for i in range(1, n+1):
    cnts[i] = dfs(i)
mx_cnt = max(cnts)
for i, j in enumerate(cnts):
    if j == mx_cnt:
        print(i, end=" ")

마지막을 보면 탐색한 개수를 배열[노드] 형식으로 저장해주고, 나중에 가장 많이 탐색한 시작 위치를 오름차순에 맞게 출력하는 것을 볼 수 있다. 물론 인접한 노드를 순차적으로 먼저 탐색하는 너비 우선 탐색을 활용할 수도 있다.