8주차 코딩테스트 요점(dfs, bfs)

1. DFS와BFS(백준 1260)

# 35004KB 388ms
import sys
from collections import deque

N, M, V = map(int, sys.stdin.readline().strip().split(' '))
graph = {}
for _ in range(M):
    a, b = map(int, sys.stdin.readline().strip().split(' '))
    if a not in list(graph.keys()):
        graph[a] = [b]
    else:
        graph[a].append(b)

    # 양방향 그래프 구현현
    if b not in list(graph.keys()):
        graph[b] = [a]
    else:
        graph[b].append(a)
visited = [False] * (N + 1)
list1 = []
# print(graph)
# print("------------------------------")
# 너비우선
def dfs(graph, start, visited):
    visited[start] = True
    print(start, end=' ')
    if start in list(graph.keys()):
        list1 = graph[start]
        list1.sort()
        for i in list1:
            if visited[i] == False:
                dfs(graph, i, visited)

dfs(graph,V,visited)

print()

visited2 = [False] * (N + 1)
def bfs(graph, start, visited):
    visited[start] = True
    print(start, end=' ')
    if start in list(graph.keys()):
        listt = graph[start]
        listt.sort()
        queue = deque(listt)

        while queue:
            a = queue.popleft()
            if visited[a] == False:
                visited[a] = True
                print(a, end=' ')
                if a in list(graph.keys()):
                    listt = graph[a]
                    listt.sort()
                    queue.extend(listt)
bfs(graph,V,visited2)

 

BFS는 Breadth-First Search 로 너비를 우선적으로 탐색하는 방식입니다. 

반면 DFS는 Depth-First Search 로 깊이를 우선적으로 탐색하는 방식입니다. 

매우 중요한 내용이므로 무슨 방식이고 어떤 코드로 구현 할 수 있는지 아는게 중요한거 같습니다. 

 

2. 그 밖에 푼 문제

10451_순열_사이클

coding_test_study/week_4/10451_순열_사이클 at main · wonwookim/coding_test_study

 

1991_트리_순회

coding_test_study/week_4/1991_트리_순회 at main · wonwookim/coding_test_study

2606_바이러스

coding_test_study/week_4/2606_바이러스 at main · wonwookim/coding_test_study

모두 위 개념을 이해하면 풀 수 있는 문제들입니다.