[python]1260_DFS와 BFS

사용한 자료구조 및 개념 : DFS, BFS, deque

 

💡 문제풀이 아이디어 및 어려웠던 점

💫 아이디어

1️⃣ dfs를 재귀로 구현한다.

2️⃣ bfs를 deque을 사용하여 구현한다.

---

👻 어려웠던 점

🚨 문제 틀림

❓이유

: 문제의 요구사항에서 낮은 번호를 우선으로 방문해야 한다는 것을 놓쳤다..!

 

❗해결 :

graph = [sorted(g) for g in graph]

를 추가하였다!

 

---

 

Solution Code & 주석

import sys
from collections import deque

input = sys.stdin.readline

def dfs(graph, start, visited):
    visited[start] = True
    result = [start]

    for next_node in graph[start]:
        if not visited[next_node]:
            result.extend(dfs(graph, next_node, visited))
    return result

def bfs(graph, start, visited):
    visited[start] = True
    result = [start]
    queue = deque([start])

    while queue:
        node = queue.popleft()
        for next_node in graph[node]:
            if not visited[next_node]:
                visited[next_node] = True
                result.append(next_node)
                queue.append(next_node)
    return result

n, m, v = map(int, input().split())
graph = [[] for _ in range(n + 1)]
dfs_visited = [False] * (n + 1)
bfs_visited = [False] * (n + 1)

for _ in range(m):
    v1, v2 = map(int, input().split())
    graph[v1].append(v2)
    graph[v2].append(v1)

graph = [sorted(g) for g in graph]

print(*dfs(graph, v, dfs_visited))
print(*bfs(graph, v, bfs_visited))