[Python] 백준 #1260 DFS와 BFS

www.acmicpc.net/problem/1260

1260번: DFS와 BFS

 

# BFS

from collections import deque

def BFS(graph,start):
    
    for key in graph:
        graph[key].sort()
    
    visited=[0 for i in range(a)]
    
    queue=deque()
    
    queue.append(start)
    
    while queue: #큐 안에 원소가 있는 동안
        k=queue.popleft()
        
        for i in graph[k]:
            if(visited[k-1]==0):
                queue.append(i) #연결된 노드 삽입
        
        if(visited[k-1]==0): #방문 안했으면 print
            print(k,end=' ')
            
        visited[k-1]=1 #방문 체크

# DFS

#넣고 빼고 연결 넣고 출력

def DFS(graph,start):
    
    for key in graph:
        graph[key].sort(reverse=True)
        
    stack=[start]
    visited=[0 for i in range(a)]
    
    while stack:
        k=stack.pop()
        for i in graph[k]:
            if(visited[k-1]==0):
                stack.append(i)
        if(visited[k-1]==0):
            print(k,end=' ')     
        visited[k-1]=1


a,b,c=map(int,input().split()) #정점 개수,간선 개수, 탐색 시작 번호
graph={i:[] for i in range(1,a+1)}
for i in range(b):
    x,y=map(int,input().split())
    graph[x].append(y)
    graph[y].append(x)
    
DFS(graph,c)
print('')
BFS(graph,c)