백준-1260(DFS, BFS)

문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

---

이론

정렬된 데이터를 이분탐색처럼 효율적(O(logN)으로 검색하는 방법이 있기도 하지만,

모든 경우의 수를 탐색해야하는 경우도 있다. ex) 알파고

DFS와 BFS는 탐색하는 순서의 차이가 있다.

DFS는 끝까지 파고드는 것이고, BFS는 갈라진 모든 경우의 수를 탐색하는 방법이다.

DFS(Depth First Search)

• 갈 수 있는 만큼 계속 해서 탐색하다 갈 수 없게 되면 다른 방향으로 다시 탐색하는 구조.
• DFS의 반복 방식은 방문하지 않은 원소를 계속해서 찾아가면 된다.
• 그렇다면 방문하지 않았다는 조건은 어떻게 알 수 있을까?? 다 기록 해야됨.

DFS 순서
1. 루트 노드부터 시작한다
2. 현재 방문한 노드를 visited에 추가한다.
3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드에 방문한다.
4. 다시 2번부터 반복

graph = {
    1: [2, 5, 9],
    2: [1, 3],
    3: [2, 4],
    4: [3],
    5: [1, 6, 8],
    6: [5, 7],
    7: [6],
    8: [5],
    9: [1, 10],
    10: [9]
}
visited = []

1. 루트노드는 1번
2. 1을 visited에 추가한다
3. 1과 인접한 2,5,9 에서 먼저 2에 방문한다.
4. 2를 visited에 추가한다
5. 2와 인접한 1,3 중에 방문하지 않은 3에 방문한다.
6. 3을 visited에 추가한다
7. 3과 인접한 2,4 중에 방문하지 않은 4에 방문한다. #visited = [1,2,3,4]
8. 4와 인접한 3 중에 방문하지 않은 노드는 없다. 
9. 3과 인접한 2,4중에 방문하지 않은 노드는 없다.
10. 2와 인접한 1,3중에 방문하지 않은 노드는 없다.
11. 1과 인접한 2, 5, 9중에 방문하지 않은 5를 방문한다.
12. 5를 visited에 추가한다.	#visited = [1,2,3,4,5]
13. 5와 인접한 1,6,8 중에 방문하지 않은 6을 방문 한다.
14. 6을 visited에 추가한다. #visited = [1,2,3,4,5,6]
15. 6과 인접한 5,7 중에 방문하지 않은 7을 방문한다
16. 7을 visited에 추가한다. #visited = [1,2,3,4,5,6,7]
17. 7과 인접한 6 중에 방문하지 않은 노드는 없다
18. 6과 인접한 5,7중에 방문하지 않은 노드는 없다
19. 5와 인접한 1,6,8중에 방문하지 않은 8에 방문한다.
20. 8을 visited에 추가한다 #visited = [1,2,3,4,5,6,7,8]
21. 8과 인접한 5 중에 방문하지 않은 노드는 없다
22. 5와 인접한 1,6,8 중에 방문하지 않은 곳은 없다
23. 1과 인접한 2,5,9 중에 방문하지 않은 9를 방문한다.
24. 9를 visited에 추가한다. #visited = [1,2,3,4,5,6,7,8,9]
25. 9와 인접한 노드 1,10 중에 방문하지 않은 10을 방문한다.
26. 10을 visited에 추가한다. #visited = [1,2,3,4,5,6,7,8,9,10]
27. 10과 인접한 9 중에 방문하지 않은 곳은 없다
28. 9와 인접한 1,10중에 방문하지 않은 곳은 없다.

# 스택을 이용한 DFS구현

#1. 루트 노드를 스택에 넣는다
#2. 현재 스택의 노드를 빼서 visited에 추가한다
#3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드를 스택에 추가한다.
#4. 2부터 반복
#5. 스택이 비면 졸료

graph = {
    1: [2, 5, 9],
    2: [1, 3],
    3: [2, 4],
    4: [3],
    5: [1, 6, 8],
    6: [5, 7],
    7: [6],
    8: [5],
    9: [1, 10],
    10: [9]
}


def dfs_stack(adjacent_graph, start_node):
    stack = [start_node]
    visited = []

    while stack:
        current_node = stack.pop()
        visited.append(current_node)
        for adjacent_node in adjacent_graph[current_node]:
            if adjacent_node not in visited:
                stack.append(adjacent_node)
    return visited


print(dfs_stack(graph, 1))  # 1 이 시작노드입니다!

 

 

BFS(Breadth-First Search)

BFS는 현재 인접한 노드 먼저 방문해야 한다.

인접한 노드 중 방문하지 않은 모든 노드들은 저장해 두고,

가장 처음에 넣은 노드를 꺼내서 탐색하면 된다.

큐를 이용해서 BFS를 구현 해보자

1. 루트 노드를 큐에 넣는다
2. 현재 큐의 노드를 빼서 visited에 넣는다
3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드를 큐에 추가한다.
4. 2번부터 반복


graph = {
    1: [2, 3, 4],
    2: [1, 5],
    3: [1, 6, 7],
    4: [1, 8],
    5: [2, 9],
    6: [3, 10],
    7: [3],
    8: [4],
    9: [5],
    10: [6]
}


def bfs_queue(adj_graph, start_node):
    queue = [start_node]
    visited = []

    while queue:
        current_node = queue.pop(0)
        visited.append(current_node)
        for adj in adj_graph[current_node]:
            if adj not in visited:
                queue.append(adj)
    return visited


print(bfs_queue(graph, 1))  

 

---

풀이

import sys
M, N, V = map(int, sys.stdin.readline().split())
matrix = [[0] * (M+1) for i in range(M+1)]

visited = [0 for i in range(M+1)]

for i in range(N):
    a, b = map(int, sys.stdin.readline().split())
    matrix[a][b] = 1
    matrix[b][a] = 1


def dfs(matrix, start):
    print(start, end=' ')
    visited[start] = 1
    for i in range(M+1):
        if visited[i] == 0 and matrix[start][i] == 1:
            dfs(matrix, i)


def bfs(matrix, start):
    queue = [start]
    visited[start] = 0

    while queue:
        current = queue.pop(0)

        print(current, end=' ')
        for i in range(M+1):
            if visited[i] == 1 and matrix[current][i] == 1:
                queue.append(i)
                visited[i] = 0


dfs(matrix, V)
print()
bfs(matrix, V)