0%

[백준/1260] DFS와 BFS

작성일 Edited on In Disqus:

Baekjoon Online Judge - 1260

  • BFS는 쉽게 했는데 DFS에서 삽질을 많이 했다. 자꾸 1>4>3>2가 출력되길래…
  • 작은 노드부터 탐색을 해야하기 때문에, dfs 함수 내에서 작은 노드부터 탐색할 수 있게끔 자식 노드를 정렬해 스택에 넣어줘야 한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
import collections

def dfs(v):
    stack = []

    # 스택과 visited 리스트에 루트 노드 추가
    visited = [v]
    # 작은 노드부터 탐색해야하기 때문에 정렬
    stack.extend(reversed(adj[v]))

    while stack:
        # 제일 위에 있는 노드 꺼내기
        node = stack.pop()
        # 해당 노드가 방문하지 않은 노드일 경우
        if node not in visited:
            # 해당 노드를 visited 리스트에 추가
            visited.append(node)
            # 해당 노드의 자식노드를 스택에 추가
            # 작은 노드부터 탐색해야하기 때문에 정렬
            stack.extend(reversed(adj[node]))
    return visited

def bfs(v):
    queue = collections.deque()

    # 큐와 visited 리스트에 루트 노드 추가
    visited = [v]
    queue += adj[v]

    while queue:
        # 먼저 큐에 들어가있던 노드 꺼내기
        node = queue.popleft()
        # 해당 노드가 방문하지 않은 노드일 경우
        if node not in visited:
            # 해당 노드의 자식노드를 큐에 추가
            queue += adj[node]
            # 해당 노드를 visited 리스트에 추가
            visited.append(node)

    return visited

N, M, V = (map(int, input().split()))

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

for _ in range(M):
    a, b = (map(int, input().split()))
    adj[a].append(b)
    adj[b].append(a)

    # 정점 번호가 작은 순대로 정렬
    adj[a].sort()
    adj[b].sort()

# 배열을 문자열로 변환
answer1 = " ".join(str(x) for x in dfs(V))
answer2 = " ".join(str(x) for x in bfs(V))

print(answer1)
print(answer2)