[알고리즘][파이]1260-DFS와 BFS ✅

 

 

문제

 

코드

import sys
from collections import deque

N,M,V = map(int,sys.stdin.readline().strip().split())

graph =[[] for _ in range(N+1)]

def dfs(cur_v):
    visited.append(cur_v)
    for v in graph[cur_v]:
        if(v not in visited):
            dfs(v)
    return visited    

def bfs(start_v):
    visited=[start_v]
    q = deque() 
    q.append(start_v)
    while(q):
        cur_v =q.popleft()
        for v in graph[cur_v]:
            if(v not in visited):
                visited.append(v)
                q.append(v)
    return visited


for i in range(M):
    a,b = map(int,sys.stdin.readline().strip().split())
    #if(a not in graph): graph[a]=list()
    #if(b not in graph): graph[b]=list()  #딕셔너리로 풀려면 필요한 코드
    graph[a].append(b)
    graph[b].append(a)

for i in graph:
    i.sort()

visited=[]
print(*dfs(V))
visited = [False]*(N+1)
print(*bfs(V))  #*을 붙이면 데이터 이외의 요소를 제거할 수 있다.

DFS와 BFS의 기본적인 코드를 요구하는 문제이다.

 

+풀면서 겪은 일

 

#처음에 시간복잡도를 줄일 수 있는 딕셔너리를 이용해서 풀려다가 빠른 sort()처리를 위해 이중 배열로 바꿔서 풀었다.

 

#딕셔너리는 바로 append가 불가능 해서 데이터를 담을 때 아무 것도 없는  list()로 초기화해주는 코드가 필요하다.

 

#반면 이중 배열을 사용할 때는 바로 append를 사용할 수 있다.