2606번 바이러스

문제 출처 : https://www.acmicpc.net/problem/2606

정말 기본적인 탐색 문제
탐색 알고리즘에 어떠한 변형도 없이 작성해서 몇 번 NODE를 지나치는지만 count 해주면 된다.
DFS로도 풀어보고 BFS로도 풀이 가능. 간선(EDGE)를 표현하는 구조도 dictionary가 탐색할때 O(1)이라 효율적일 줄 알았는데 그렇지도 않다. 왜지?
그래서 간선을 표현할 수 있는 dictionary, 2차원 배열 두가지 방식을 사용하여 작성해봤다.

1. DFS

import sys

N= int(sys.stdin.readline().rstrip("\n"))
e_num = int(sys.stdin.readline().rstrip("\n"))
e = [[] for _ in range(N+1)]
visited = [0 for _ in range(101)]

for _ in range(e_num) :
    a,b = list(map(int,sys.stdin.readline().rstrip("\n").split()))
    e[a].append(b)
    e[b].append(a)

visited[1] = 1
count = 0

def dfs(s) :
    global count
    for next_s in e[s] :
        if not visited[next_s] :
            visited[next_s]+=1
            count+=1
            dfs(next_s)
dfs(1)
print(count)

2. BFS ( 2차원 배열 )

import sys
from collections import deque

N= int(sys.stdin.readline().rstrip("\n"))
e_num = int(sys.stdin.readline().rstrip("\n"))
e = [[] for _ in range(N+1)]
visited = [0 for _ in range(101)]

for _ in range(e_num) :
    a,b = list(map(int,sys.stdin.readline().rstrip("\n").split()))
    e[a].append(b)
    e[b].append(a)

dq = deque([1])
visited[1] = 1
count = 0

def virus() :
    global count
    while dq :
        s=dq.popleft()
        for next_c in e[s] :
            if not visited[next_c]:
                visited[next_c]+=1
                count+=1
                dq.append(next_c)
virus()
print(count)

3. BFS ( defaultdict )

import sys
from collections import defaultdict
from collections import deque

N= int(sys.stdin.readline().rstrip("\n"))
e_num = int(sys.stdin.readline().rstrip("\n"))
e = defaultdict(list)
for _ in range(e_num) :
    i,j = list(map(int,sys.stdin.readline().rstrip("\n").split()))
    if i in e[j] :
        continue
    e[i].append(j)
    e[j].append(i)

dq = deque([1])
visited = [0 for _ in range(101)]
visited[1] = 1
count = 0

def virus() :
    global count
    while dq :
        s=dq.popleft()
        for next_c in e[s] :
            if not visited[next_c]:
                visited[next_c]+=1
                count+=1
                dq.append(next_c)
virus()
print(count)

3가지 방식에 대한 시간과 메모리를 살펴보면

와 3 사이에서는 유의미하다고 느껴지는 차이가 없지만 1에서는 유의미할 정도의 차이가 발생했다. 모든 node를 탐색하며 count하는 문제인만큼 이런 문제에서는 BFS보다 DFS가 더 빠르게 순환할 수 있는 걸까? 다른 문제들을 풀어보면서 연역적으로 결론내봐야겠다. ( 실제로 구조 자체도 BFS보다 DFS가 더 간단하긴 하다.)

어제도 봤듯이 사실 BFS는 최단 경로, 특수한 경로를 찾는 문제에서 좀 더 유리하단다