[99클럽 코티 스터디 TIL 6일차 / 백준 1260] DFS와 BFS (Python)

 

이 문제는 DFS와 BFS 그래프 탐색을 이요해서 푸는 문제이다.

 

일단 DFS와 BFS의 개념에 대해서 알아보겠다.

 

깊이 우선 탐색 (DFS, Depth-First-Search)

- 루트 노드에서 시작해서 다음 분기를 넘어가기 전까지 해당 분기의 모든 노드를 탐색

- 탐색할때 한 방향으로 더이상 탐색할게 없을때까지 탐색한 후 돌아와 다른 방향 다시 탐색

- 모든 노드를 탐색해야 하는 경우에 적합

- 속도는 BFS보다 느림

- 순환 알고리즘 형태, 재귀함수 사용O

 

넓이 우선 탐색 (BFS, Breadth-First-Search)

- 루트 노드에서 시작하여 인접한 노드를 순서대로 탐색

- 탐색할때 가까운 노드를 먼저 방문하고 먼 노드를 나중에 탐색

- 두 노드 사이의 최단 거리 또는 경로를 구하는 경우에 적합

- 재귀함수 사용X

 

내 코드

# DFS
n, m, v = map(int, input().split())

graph = [[] for i in range(n+1)]
visited = [False] * (n+1)

for j in range(1, m+1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

graph = list(map(sorted, graph))

def DFS(graph, v, visited):
    visited[v] = True
    print(v, end=' ')

    for k in graph[v]:
        if not visited[k]:
            DFS(graph, k, visited)

DFS(graph, v, visited)
print("")

#BFS
from collections import deque

visited = [False] * (n+1)
def BFS(graph, root, visited):
    queue = deque([root])
    visited[root] = True
    
    while queue:
        node = queue.popleft()
        print(node, end=' ')
        
        for i in graph[node]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

BFS(graph, v, visited)

 

DFS함수는 재귀함수를 이용하여 한 방향에 있는 노드를 모두 탐색한 뒤에 다음 방향을 탐색하도록 구현하였다. 

 

BFS 함순은 queue를 사용하여 순차적으로 같은 깊이의 노드를 탐색하고 점점 깊은 깊이의 노드를 탐색하도록 하였다.

 

 

나는 정말 바보다 .. 저번에 내일 배움카드 미리 발급 안해서 기회를 날려먹은거로 모자라서 이수구분 잘못해서 학교를 더 다녀야 한다... 난 이제 5학년 .. 6년째 학교다니기 .. 이건 대학교가 아니라 초등학교..?

현타와 충격이 이빠이 와서 저번주 금요일에 처음으로 99클럽 코테 스터디 미션을 못했다 ㅜㅜㅜㅜ

오늘부터 다시 마음잡고 열심히 해보자 ,,