DFS와 BFS

백준 1260

DFS와 BFS를 구현하는 문제이다.

from collections import deque

def dfs(graph, v, visited):
    visited.append(v) # visited에 넣어
    for ad in graph[v]:
        if ad not in visited:
            dfs(graph, ad, visited)
    return visited

queue = deque()
def bfs(graph, v, visited_2):
    queue.append(v) #큐에 넣고
    visited_2.append(v) #visited에도 넣어
    while queue:
        node = queue.popleft()
        for ad in graph[node]:
            if ad not in visited_2:
                queue.append(ad)
                visited_2.append(ad)
    return visited_2

n, m, v = map(int, input().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
    graph[a].sort()
    graph[b].sort()

visited = []
print(*dfs(graph, v, visited))
visited_2 = []
print(*bfs(graph, v, visited_2))

입력받은 수를 서로의 리스트(graph)에 담아주었고, graph의 0번째에는 빈 리스트를 두었다. DFS : v를 visited에 넣고, v의 이웃들 중에서 visited에 없는 이웃들을 다시 dfs로 돌린다. BFS : v를 큐에 넣고 visited에도 넣는다. 큐가 비어있지 않을 동안 큐에서 팝한 노드의 이웃들 중 visited에 없으면 큐에 넣고 visited에 넣는다.

파이썬에서 1차원 리스트의 원소만 출력하고 싶을 때는 리스트 이름 앞에 별(*)을 붙여주면 된다!