DFS, BFS (백준 1260 파이썬)

DFS (Depth First) : 루트부터 시작해서 한 브랜치의 자식 노드를 모두 파악한 뒤 다음 브랜치로 넘어가며 탐색

 

DFS의 예시 - 미로탐색에서 한 길을 쭉 본다음 길이 없으면 그다음 갈림길로 돌아와서 다시 쭉 탐색하는 방식. BFS보다 간단하며 BFS보다 느리다. 모든 노드를 탐색하고자 할 때 사용한다.

DFS 구현 - 스택과 재귀함수로 구현한다.

 

BFS (Breadth First) : 루트부터 시작해서 각 브랜치의 level 별로 인접한 노드를 먼저 탐색

 

BFS 예시 - 두 노드 사이의 최단 경로를 찾을 때 사용. DFS보다 복잡하지만 빠르다. 

BFS 구현 - 큐로 구현한다.

 

어떤 문제에서 사용해야 할까?

 

1. 그래프의 모든 정점을 방문해야 하는 문제 > 둘 다 가능.

2. 경로의 특징을 저장-활용해야 하는 문제, 제약조건이 있는 문제 ex) 경로에서 노드의 값이 중복되는 값이 있으면 안된다~ 등. > DFS 사용

3. 최단거리 구해야 하는 문제 > BFS 사용. 현재 노드에서 가까운 곳부터 (값이 작은 곳부터) 찾기에 그게 최솟값이다.

 

 

백준 1260 파이썬 풀이

 

 

첫번째 입력은 정점, 간선, 시작 번호이다.

각 변수 N, M, V로 인풋을 받아주자.

 

그다음 M개의 인풋은 정점 간 간선을 의미한다.

이를 표현하기 위해 2차원 NxN zero metric으로 그래프를 표현하고, 각 인풋에 해당하는 좌표를 1로 만들어줌으로써 간선이 연결됨을 표기한다.

 

그 뒤, dfs와 bfs를 위한 방문 리스트를 만들어준다.

N,M,V = map(int,input().split())

# zero metric
graph = [[0]*(N+1) for _ in range(N+1)]

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

# visited list
visited1 = [0]*(N+1)
visited2 = [0]*(N+1)

 

dfs를 만든다.

함수 실행 시 visited에 값을 넣고, 재귀를 통해 탐색할 수 있도록 한다.

이때 loop와 조건문으로 간선이 있고, 방문한 적이 없는 정점을 찾는다.

def dfs(V):
    visited1[V] = 1
    print(V, end=' ')
    for i in range(1, N+1):
        if graph[V][i] == 1 and visited1[i] == 0:
            dfs(i)

 

bfs는 큐로 만들 수 있다. while queue:를 통해 queue가 빌 때 까지 탐색을 수행한다.

def bfs(V):
    queue = [V]
    visited2[V] = 1 #방문처리
    while queue:
        V = queue.pop(0) #방문 노드 제거
        print(V, end = ' ')
        for i in range(1, N+1):
            if(graph[V][i] == 1 and visited2[i] == 0):
                queue.append(i)
                visited2[i] = 1 # 방문처리

dfs(V)
print()
bfs(V)