[백준] 1260번 DFS와 BFS: Python

 

 

 

문제 해결 포인트

DFS와 BFS의 기본 개념을 알고 있어야 합니다.

 

DFS

1. 깊이 우선 탐색입니다.

2. 어느 한 방향(branch)으로 깊게 탐색하다가 해를 찾지 못하면 부모 노드로 돌아와서 다음 노드를 탐색합니다.

3. 따라서 재귀함수와 스택으로 구현해야 합니다.

4. 현재 방향의 노드들만을 저장하기 때문에 메모리 관리 측면에서는 효율적입니다.

5. 그러나 목표 노드가 너무 깊이 있으면 해를 구하는데 시간이 오래 걸립니다.

6. 한 방향에서 해를 찾으면 바로 빠져나오기 때문에, 다른 방향으로 구하는 해를 검증할 수가 없습니다. 따라서 최적의 해가 아닐 수도 있습니다.

 

BFS

1. 너비 우선 탐색입니다.

2. 노드와 인접한 노드들부터 차례대로 탐색합니다.

3. 따라서 반복문과 큐로 구현해야 합니다.

4. 인접한 노드 전부를 탐색하기 때문에, DFS보다 많은 메모리를 필요로 합니다.

5. 인접한 노드 순서대로 탐색하기 때문에 최단 경로를 보장하게 됩니다.

 

 

결국 핵심은 2가지입니다. 이 2가지를 재귀/반복문, 스택/큐에 맞게 적절히 구현하는것이 포인트입니다.

1. 방문한 노드를 다시 방문하지 않도록 한다.

2. 해를 찾으면 탐색을 중단하고 적당한 단계에서 빠져나와야 한다.

 

 

코드 작성

import sys
from collections import deque

input = sys.stdin

N, M, V = map(int, input.readline().split())
graph = [[] for _ in range(N)]

for _ in range(M):
    v1, v2 = map(int, input.readline().split())
    graph[v1-1].append(v2)
    graph[v2-1].append(v1)

for g in graph:
    g.sort()


#DFS
DFSvisited = []

def DFS(visiting):
    DFSvisited.append(visiting)
    candidates = []
    for i in graph[visiting-1]:
        if i not in DFSvisited:
            candidates.append(i)

    for candidate in candidates:
        if candidate not in DFSvisited:
            DFS(candidate)

DFS(V)

DFSvisited = " ".join([str(x) for x in DFSvisited])
print(DFSvisited)



#BFS
BFSvisited = []

def BFS(start):
    queue = deque([start])

    while queue:
        visiting = queue.popleft()
        BFSvisited.append(visiting)

        candidates = graph[visiting-1]
        for candidate in candidates:
            if candidate not in BFSvisited and candidate not in queue:
                queue.append(candidate)


BFS(V)

BFSvisited = " ".join([str(x) for x in BFSvisited])
print(BFSvisited)