[Python] 백준1260 (DFS와 BFS) - 파이썬 문제 풀이

DFS와 BFS (백준)
문제 - https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

 

DFS(Depth First Search)의 특징

• 깊이를 우선적으로 탐색하는 알고리즘입니다.
• 자기 자신을 호출하는 순환 알고리즘의 형태를 가지며, 주로 재귀함수를 사용합니다.

 

BFS(Breadth First Search)의 특징

• 그래프에서 시작점 노드 기준으로 인접한 노드부터 탐색하는 알고리즘입니다.
• 인접한 노드부터 차례로 탐색하며, 방문한 노드들을 차례로 저장한 후 pop을 이용하여 차례로 노드를 꺼내서 체크할 수 있는 자료구조 큐(Queue)를 사용합니다.

 

문제 풀이:

• DFS는 재귀함수를 이용하여 차례로 노드의 방문한 깊이까지 확인합니다.
• BFS는 자료구조인 Deque를 이용하여 

from collections import deque

def dfs(v):
    print(v, end=' ')
    visited[v] = True
    
    for node in adj[v]:
        if not visited[node]:
            dfs(node)


def bfs(v):
    queue = deque([v])
    while queue:
        node = queue.popleft()
        if not visited[node]:
            visited[node] = True
            print(node, end=' ')
            for k in adj[node]:
                if not visited[k]:
                    queue.append(k)

# 4 5 1 , 4 node - 5 edge - start 1 node
n, m, v = map(int, input().split())
adj = [ [] for _ in range(n+1)]

for _ in range(m):
    x, y= map(int, input().split())
    adj[x].append(y)
    adj[y].append(x)
 
visited = [False] * (n+1)
bfs(v)

visited = [False] * (n+1)
dfs(v)

 

백준 문제를 통해 dfs bfs에 대해 알아보았습니다.

기본적인 dfs와 bfs에 대해 이해를 한다면, 응용 문제에서도 충분히 풀 수 있을 것이라고 생각합니다.!