DFS와 BFS

1260번: DFS와 BFS

 

나의 풀이

from collections import deque
import sys
input = sys.stdin.readline

p_ct, l_ct, start = list(map(int, input().rstrip().split()))

def bfs(conn_dict, v_len, v_s):
    visit = [0] * v_len
    v_seq = []
    queue = deque([v_s])

    visit[v_s - 1] = 1
    while queue:
        n_v = queue.popleft()
        v_seq.append(str(n_v))
        
        next_list = sorted(conn_dict[n_v])
        for next_v in next_list:
            if visit[next_v - 1] == 0:
                visit[next_v - 1] = 1
                queue.append(next_v)
    
    return ' '.join(v_seq)

def dfs(conn_dict, v_len, v_s):
    visit = [0]*v_len
    v_seq = []
    stack = [v_s]
    
    while stack:
        n_v = stack.pop()
        if visit[n_v-1] == 0:
            visit[n_v-1] = 1
            v_seq.append(str(n_v))
        
            next_list = sorted(conn_dict[n_v], reverse=True)
            for next_v in next_list:
                if visit[next_v-1] == 0:
                    stack.append(next_v)
        
    return ' '.join(v_seq)

# 연결 정보 딕셔너리 초기화
conn_dict = {i: [] for i in range(1, p_ct + 1)}

for _ in range(l_ct):
    s, e = map(int, input().split())
    conn_dict[s].append(e)
    conn_dict[e].append(s)

print(dfs(conn_dict, p_ct, start))
print(bfs(conn_dict, p_ct, start))

 

 

시간 복잡도

conn_dict : 연결 정보 생성 ( 선형 시간 복잡도 )
bfs, dfs : 모든 간선을 순회 하므로 ( 선형 시간 복잡도 )
해당 알고리즘은 선형 시간 복잡도 ( O(n) )