[Python] 백준 1260 DFS와 BFS

https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

 

문제

 

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

 

코드 

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

n, m, v = map(int, input().split())

adjArray = [[False] * n for _ in range(n)]

checkArray_dfs = [False] * n
checkArray_bfs = [False] * n

for _ in range(m):
    a, b = map(int, input().split())

    a -= 1
    b -= 1

    adjArray[a][b] = True
    adjArray[b][a] = True

def dfs(currentNode):       
    checkArray_dfs[currentNode] = True    
    print(currentNode + 1, end = " ")  
    
    for nextNode in range(n): 
        if not checkArray_dfs[nextNode] and adjArray[currentNode][nextNode] == True:
            dfs(nextNode)
            
        
def bfs(currentNode):
    checkArray_bfs[currentNode] = True
    q = deque()
    q.append(currentNode)

    while q:
        currentNode = q.popleft()
        print(currentNode + 1, end = " ")

        for nextNode in range(n):
            if not checkArray_bfs[nextNode] and adjArray[currentNode][nextNode] == True:
                q.append(nextNode)
                checkArray_bfs[nextNode] = True
                
                
dfs(v-1)
print()
bfs(v-1)