[python] 그래프와 순회(BFS, DFS)_백준 문제풀이

bfs와 dfs는 그래프 탐색 알고리즘으로, 문제를 풀 때 상당히 많이 사용한다.

그래프란? 여러 개체들이 연결되어 있는 자료구조
탐색이란? 특정 개체를 찾는 것

대표적인 문제 유형
1. 경로 탐색 유형 (최단거리, 시간)
2. 네트워크 유형 (연결, 그룹 개수)
3. 조합 유형 (모든 조합 구하기)

DFS

루트 노드 혹은 임의 노드에서 다음 브랜치로 넘어가기 전에, 해당 브랜치를 모두 탐색하는 방법
스택보다는 재귀함수를 통해 구현하는 것이 일반적이고, 재귀를 타고 타고 가서 탈출 조건에 먼저 도달하도록 한다.

모든 경로를 방문해야 할 경우 사용에 적합

시간 복잡도
인접 행렬 : O(V^2)
인접 리스트 : O(V+E)
V는 접점, E는 간선을 뜻한다

BFS

루트 노드 또는 임의 노드에서 인접한 노드부터 먼저 탐색하는 방법
일반적으로 큐를 통해 구현한다. (해당 노드의 주변부터 탐색해야하기 때문)
1. 가장 먼저 넣었던 것을 꺼내서
2. 거기에 연결된 점을 큐에 넣기
3. 큐가 빌 때까지 계속 반복

최소 비용(즉, 모든 곳을 탐색하는 것보다 최소 비용이 우선일 때)에 적합

시간 복잡도
인접 행렬 : O(V^2)
인접 리스트 : O(V+E)

그렇다면 dfs/bfs 중 어떤 걸 사용해야 할까?

둘다 탐색 알고리즘이기 때문에 무엇을 선택하던지 풀 수 있다.
직관적으로 해결해갈 수 있는 dfs를 더 선호하지만, bfs가 필요할 때가 있다.
bfs가 시간 복잡도가 낮다. dfs는 대박/쪽박 가능, bfs는 둘다 x

코딩테스트에는 극악의 케이스가 포함된다.
효율성 tc에서 걸리기 때문에, 고난이도로 보이는 문제는 dfs로 풀어야 한다.

(dfs) 백준 24479번 - 깊이 우선 탐색 1

문제 링크 - [https://www.acmicpc.net/problem/24479]

import sys
sys.setrecursionlimit(10 ** 6)  # 재귀 허용 깊이를 수동으로 늘려주는 코드
#정점의 수,간선의 수,시작 정점
n,m,r= map(int,sys.stdin.readline().split())
#연결노드 그래프 초기화(1번노드와 인덱스 값이 같게 하기 위해서 n+1로 )
#[[],[],[],[],[],[]]
graph=[[] for _ in range(n+1)]
#방문 순서 그래프 (이것도 인덱스 값과 노드의 값이 동일하게 만드릭 위해서 설정 )
visted =[0]*(n+1)
# 순차 입력
cnt=1
def dfs(graph,v,visted):
    #함수 밖에 cnt값을 쓰기 위해서 global이라고 명시
    global cnt
    #방문할 때마다 순차 값 변경
    visted[v]=cnt
    #연결된 노드 방문
    for i in graph[v]:
        #방문 안한 노드일 경우
        if visted[i]==0:
            #순차 증가
            cnt+=1
            #dfs 실행
            dfs(graph,i,visted)

#연결된 노드 입력 받기
for i in range(m):
    u,v = map(int,sys.stdin.readline().split())
    graph[u].append(v)
    graph[v].append(u)
 
#오름차순 정리
for i in range(n+1):
    graph[i].sort()
 
 
dfs(graph,r,visted)
#순차 출력
for i in range(n+1):
    if i!=0:
        print(visted[i])

DFS와 BFS

문제 링크 - [https://www.acmicpc.net/problem/1260]

from collections import deque
import sys
n,m,r = map(int,sys.stdin.readline().split())
graph = [[] for _ in range(n+1)]

for i in range(m):
   u, v = map(int, sys.stdin.readline().split())
   graph[u].append(v)
   graph[v].append(u)

visited_dfs = [0]*(n+1)
visited_bfs = [0]*(n+1)
count_dfs = 1
count_bfs = 1

def dfs(v):
   global visited_dfs, count_dfs
   print(v, end = ' ')
   visited_dfs[v] = 1
   if count_dfs == n:
       return
   arr = sorted(graph[v])
   for x in arr:
       if visited_dfs[x] == 0:
           count_dfs += 1
           dfs(x)
       else:
           continue
queue = deque()
def bfs(v):
   global visited_bfs, count_bfs
   arr = sorted(graph[v])
   for x in arr:
       if visited_bfs[x] == 0:
           print(x, end=' ')
           visited_bfs[x] = 1
           queue.append(x)
           count_bfs += 1
   if count_bfs == n:
       return
   while queue:
       bfs(queue.popleft())


dfs(r)
print()
print(r, end = ' ')
visited_bfs[r] = 1
bfs(r)