[DFS, BFS] 백준 1260. DFS와 BFS

깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)

BFS 코드의 프레임 특징

from collections import deque

...

def BFS(v):

    q = deque()

    q.append(v)

    while q:

        p = q.popleft()

        print(p)

 

 

from collections import deque
import sys
sys.stdin = open('C:\\tech\\backjoon\\graph\\input3.txt','r')
input = sys.stdin.readline

res = []
def DFS(node):
    visit1[node] = 1
    line = graph[node]
    for i in range(1,n+1):
        if line[i] == 1 and visit1[i] == 0:
            if i not in res:
                res.append(i)
            DFS(i)

def BFS(node):
    q = deque()
    q.append(node)
    visit2[node] = 1
    while q:
        v = q.popleft()
        print(v, end = ' ')
        for i in range(1, n+1):
            if visit2[i] == 0 and graph[v][i] == 1:
                q.append(i)
                visit2[i] = 1


n,m,v = map(int, input().split())
# g = [[map(int, input().split())] for _ in range())]

graph = [[0]*(n+1) for _ in range(n+1)]
visit1 = [0]*(n+1)
visit2 = [0]*(n+1)

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

res.append(v)
DFS(v)
for r in res:
    print(r, end = ' ')
print()
BFS(v)

 

 

* Brute-force 탐색

BFS랑 같은 건 줄 알았는데, 전혀 아니다. Brute Force는 무자비하게 전부 탐색하는 방식으로, 값을 구하기 위해 하나씩 다 대입해보는 것이다.