[백준/python] 1260 dfs와 bfs

1260번: DFS와 BFS (acmicpc.net)

import sys
input = sys.stdin.readline
n,m,v=map(int,input().split())
di={}
for _ in range(m):
    a,b=map(int,input().split())
    if a in di:
        di[a].append(b)
        di[a]=sorted(di[a], reverse=True)
    else: di[a]=[b]
    if b in di:
        di[b].append(a)
        di[b] = sorted(di[b], reverse=True)
    else: di[b]=[a]

def DFS(start): #깊이~후입선출=스택
    st=list()
    visit= {}

    st.append(start)

    while st:
        node=st.pop()
        if node in visit: continue
        visit[node] = True
        if node not in di: continue
        st.extend(di[node])

    return ' '.join(map(str,list(visit.keys())))

print(DFS(v))


def BFS(start): #너비~선입선출=큐
    q=list()
    visit= {}

    q.append(start)

    while q:
        node=q.pop(0)
        if node in visit: continue
        visit[node] = True
        if node not in di: continue
        q.extend(sorted(di[node]))

    return ' '.join(map(str,list(visit.keys())))
print(BFS(v))

 

단순히 bfs와 dfs를 보통 구현하듯 구현하면 되는 문제다. 처음 입력받을 때 서로에 대해서 모두 저장해준다. 더 작은 애 먼저 pop되기위해 내림차순 정렬을 해준다.