DFS,BFS

알고리즘의 꽃 그래프이론까지 왔다. 

https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

from collections import deque

N, M, V = map(int, input().split())  # 입력 받기
graph = [[] for _ in range(N + 1)]  # 그래프를 인접 리스트로 표현
visited = [False] * (N + 1)  # 방문 처리 배열

for _ in range(M):  # 간선 정보 입력 받아 그래프 구성
  a, b = map(int, input().split())
  graph[a].append(b)
  graph[b].append(a)  # 무방향 그래프이므로 양방향 처리

# DFS 함수
def dfs(graph, v, visited):
    visited[v] = True  # 현재 노드 방문 처리
    print(v, end=' ')  # 현재 노드 출력
    for i in sorted(graph[v]):  # 인접한 노드들을 정렬하여 순회
        if not visited[i]:  # 방문하지 않은 노드라면
            dfs(graph, i, visited)  # 재귀적으로 DFS 수행

#graph = [[], [2, 3, 4], [1, 4], [1, 4], [1, 2, 3]]

# BFS 함수
def bfs(graph, start):
    visited = [False] * (len(graph) + 1)  # 방문 처리를 위한 배열
    queue = deque([start])  # 시작 노드를 큐에 삽입
    visited[start] = True  # 시작 노드 방문 처리
    while queue:
        v = queue.popleft()  # 큐에서 하나의 원소를 뽑아 출력
        print(v, end=' ')
        for i in sorted(graph[v]):  # 인접한 노드들을 정렬하여 순회
            if not visited[i]:
                queue.append(i)  # 방문하지 않은 노드를 큐에 삽입
                visited[i] = True  # 방문 처리





dfs(graph, V, visited)  # DFS 수행
print()
bfs(graph, V)  # BFS 수행

 

보통 bfs를 쓸지, dfs를 쓸지를 어떻게 정할까? 

일단 최단경로를 찾는경우는 bfs를 사용한다. 

 

DFS

목표는 경로를 찾는 것이 아니라 단순히 어떤 노드를 방문하는 것일 때 DFS

깊은 경로를 우선 탐색하며, 스택 또는 재귀 함수를 사용하여 구현

미로에서 모든 가능한 경로를 찾아야 할 때가 아니라 특정 경로를 찾거나 조건을 만족하는 경로를 찾을 때 유용

BFS

최단 경로를 찾아야 할 때 BFS를 사용

시작 노드에서 목표 노드까지의 최소 이동 횟수를 구해야 할 때 유용

넓은 영역을 먼저 탐색하며, 큐를 사용하여 구현

미로에서 최단 경로를 찾거나 가장 가까운 노드를 찾을 때 유용

 

현재까지 그리디, 브루트포스, 자료구조, DP, (조합,배열,정렬,집합,맵,스택,큐,덱) 을 공부했는데, 역시 그래프가 쉽지 않다.

여기까지 정복한다면 유니온파인드,투포인터,분할정복, 재귀,라인스위핑에 대해 더 공부할생각이다.