[백준_python] DFS와 BFS || 1260

www.acmicpc.net/problem/1260

1260번: DFS와 BFS

깊이 우선 탐색(DFS_Depth-First Search)

: 루트 노드를 모두 완벽하게 탐색을 한 후 다음 분기로 넘어가는 방법
모든 노드를 방문 하고자 하는 경우에 이용
순환 호출 혹은 스택 이용

너비 우선 탐색(BFS_Breadth-First Search)

: 루트 노드에서 인접한 노드부터 먼저 탐색하는 방법

두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 사용
재귀적으로 동작하지 않는다. 큐를 사용

---

# DFS와 BFS

n, m, v = map(int, input().split(' '))  # n : 정점, m : 간선, v : 시작할 정점 번호

graph = [[0]*(n+1) for _ in range(n+1)]  # 인덱스값 = 정점
visited = [False] * (n+1)  # 방문여부 체크리스트

for i in range(m):  # 간선만큼
    a, b = map(int, input().split(' '))
    graph[a][b] = graph[b][a] = 1  # 두 정점을 이어준다.


def DFS(start):
    visited[start] = True
    print(start, end=" ")
    for i in range(1, n+1):  # 1부터 n까지 검사
        if visited[i] == 0 and graph[start][i] == 1:  # 방문을 하지 않았고, 간선이 있는 곳
            DFS(i)


def BFS(start):
    queue = [start]  # 큐 이용
    visited[start] = False  # DFS에서 방문한 곳을 1로 표시하여서 BFS는 0으로 표시
    while queue:
        start = queue.pop(0)
        print(start, end=" ")
        for i in range(1, n+1):
            if visited[i] == 1 and graph[start][i] == 1:
                queue.append(i)
                visited[i] = 0


DFS(v)
print()
BFS(v)

DFS와 BFS에 관련된 여러 문제들을 풀어보면서 해당 알고리즘을 적용하는 것에 익숙해져야 할 것 같다.