[파이썬/python] 백준 1260번 - DFS와 BFS

import sys

# DFS
ansDFS = list()


def dfs(curr, val):
    if val in ansDFS:
        return
    ansDFS.append(val)
    for i in curr[]:
        dfs(edges[i-1], i)


# BFS
ansBFS = list()
queue = list()


def bfs(curr, val):
    if val in ansBFS:
        return
    ansBFS.append(val)

    for i in curr[]:
        queue.append(i)

    while len(queue) != 0:
        temp = queue.pop(0)
        bfs(edges[temp-1], temp)


N, M, V = map(int, sys.stdin.readline().split())
edges = list()
check = list()
for i in range(N):
    edges.append([])

for i in range(M):
    first, second = map(int, sys.stdin.readline().split())
    edges[first-1].append(second)
    edges[second-1].append(first)

for i in edges:
    i.sort()

dfs(edges[V-1], V)
print(*ansDFS)
bfs(edges[V-1], V)
print(*ansBFS)

자료구조, 그래프이론 문제입니다.

DFS : depth-first-search

시작 노드를 방문처리하고, 그 노드의 간선 중 최우선 노드(우선순위는 기준에 따라 달라질 수 있습니다)에 방문하는 행위를 재귀적으로 수행합니다.

 

BFS: breadth-first-search

시작 노드를 방문처리하며, 그 노드의 모든 간선들을 queue에 넣습니다.

queue가 비어있지 않다면 queue의 최우선 노드(우선순위는 기준에 따라 달라질 수 있습니다)에 방문하는 행위를 재귀적으로 수행합니다.

 

방문처리는 check 리스트에 방문했던 노드의 value를 넣어줌으로써 구현합니다.

파이썬은 for value in check: 이런식으로 리스트 안에 원소가 있는지 쉽게 체크할 수 있어서 좋군요.

 

DFS는 stack, BFS는 queue 기반입니다.

 

TIP: 문제의 출력 양식을 맞추기 위해 리스트 앞에 *을 붙입니다.

ex)

arr = [1, 2, 3, 4]

print(*arr)

 

output : 1 2 3 4

 

전 이걸 몰라서 지금껏 string으로 바꿔서 했었습니다..