[BOJ] 1260 | DFS와 BFS

아래 백준 로고를 클릭하면 해당 문제로 이동합니다 😀

풀이과정

---

DFS와 BFS 구현도 뚝딱 되는것같고 기초문제부터 다시 하니까 이해도도 올라간 느낌이랄까 ?

이번 문제는 방문 노드 순서대로 출력을 하는거다. 이전 그래프 문제들은 1번노드의 방문순서, 2번노드의 방문 순서를 쭉 출력하는게 목표였지만
이 문제는 방문한 노드를 먼저 넣고 그 순서대로 쭉 출력하는 .... (말 참 못하네 쓰고나니까 ;)

암튼 dfs_result, bfs_result를 빈 리스트로 만들고, 노드를 방문할 때 마다 해당 노드 번호를 append 해줬다.

코드

---

import sys
sys.setrecursionlimit(10**8)
from collections import deque

N, M, V = map(int, sys.stdin.readline().split())

graph = [[] for _ in range(N+1)]

for _ in range(M):
    u, v = map(int, sys.stdin.readline().split())
    graph[u].append(v)
    graph[v].append(u)

for i in range(N+1):
    graph[i].sort()

dfs_result = [] * (N+1)
bfs_result = [] * (N+1)
dfs_visited = [False] * (N+1)
bfs_visited = [False] * (N+1)

def dfs(graph, r, visited):
    visited[r] = True
    dfs_result.append(r)

    for node in graph[r]:
        if not visited[node]:
            dfs(graph, node, visited)

def bfs(graph, r, visited):
    q = deque([r])

    visited[r] = True
    bfs_result.append(r)
    
    while q:
        node = q.popleft()
        for v in graph[node]:
            if not visited[v]:
                q.append(v)
                visited[v] = True
                bfs_result.append(v)

dfs(graph, V, dfs_visited)
bfs(graph, V, bfs_visited)

print(*dfs_result)
print(*bfs_result)

결과

---