[BOJ] [Python] 1260번 : DFS와 BFS

 

BFS DFS 공부를 하면서 풀어봤다. 

DFS는 재귀함수, BFS는 deque를 이용했다.

 

 

from collections import deque

# 입력
num = list(map(int , input().split()))
n = num[0] #정점 개수
m = num[1] #간선 개수
v = num[2] #시작 정점

check = [0] * n
dic = {}

for i in range(m):
    box = list(map(int, input().split()))

    if(check[box[0]-1] == 0):
        dic[box[0]] = [(box[1])]
        check[box[0] - 1] = 1
    else:
        dic[box[0]].append(box[1])

    if(check[box[1]-1] == 0):
        dic[box[1]] = [(box[0])]
        check[box[1] - 1] = 1
    else:
        dic[box[1]].append(box[0])

# print(dic)

# 후입선출
def dfs(graph, start_n, check):

    check[start_n-1] = 1

    print(start_n, end=' ')

    for i in sorted(graph[start_n]):
        if check[i-1] == 0:
            dfs(graph, i, check)

# 선입선출
def bfs(graph, start_n, check):

    check[start_n-1] = 1
    queue = deque([start_n])

    while(queue):
        # print(queue)
        ver = queue.popleft()
        print(ver, end=' ')

        for i in sorted(graph[ver]):
            if check[i-1] == 0:

                check[i - 1] = 1

                queue.append(i)

check = [0] * n
dfs(dic, v, check)

print()

check = [0] * n
bfs(dic, v, check)