99클럽 코테 스터디 _ 6일차 TIL (DFS, BFS)

 

< 문제 >

[백준] 1260. DFS와 BFS / 실버2

---

< 풀이 >

DFS, BFS
시간복잡도 : O(V(노드 수) + E(간선 수))

from collections import deque

# DFS
def dfs(graph, v, visited):
    visited[v] = True # 현재 위치 방문 표시
    print(v, end = ' ')
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

# BFS
def bfs(graph, V, N):
    visited = [False] * (N + 1)
    q = deque([V]) # BFS 탐색 시작 위치
    visited[V] = True # 시작 위치 방문 표시
    while q:
        x = q.popleft()
        print(x, end = ' ')
        for i in graph[x]:
            if not visited[i]:
                q.append(i)
                visited[i] = True

def f():
    N, M, V = map(int, input().split())
    graph = [[] for _ in range(N+1)]
    
    for _ in range(M):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)
        
    for i in range(N+1): # 방문할 수 있는 정점이 여러 개인 경우 정점 번호가 작은 것부터 방문해야하기 떄문
        graph[i].sort()
        
    visited = [False] * (N+1)
    dfs(graph, V, visited)
    print()
    bfs(graph, V, N)

f()

• DFS
  • 현재 위치(v)를 방문 처리한다.
  • 그래프에서 v에 연결되어 있는 노드를 탐색하며 방문하지 않은 노드가 있다면 해당 노드에서 dfs 탐색을 한다.
• BFS
  • visited를 초기화한다.
  • 현재 위치(v)를 q에 넣고 방문 처리한다.
  • 그래프에서 v에 연결되어 있는 노드를 탐색하며 방문하지 않은 노드가 있다면 해당 노드를 q에 추가한다.
  • q가 비어있지 않을 때까지 q에 있는 노드 중 가장 먼저 들어온 노드를 꺼내며 방문한다.
• f()
  1. 노드와 간선을 기준으로 그래프를 생성하기 위해 graph를 빈 리스트로 생성한다.
  2. M번의 입력으로 받아온 a, b는 서로 연결되어 있는 노드이므로 각각의 graph에 연결된 노드를 추가해 준다.
  3. 방문할 수 있는 정점이 여러 개인 경우 정점 번호가 가장 작은 것부터 방문하기 위해 각 노드에 연결된 노드를 오름차순으로 정렬한다.
  4. DFS 탐색에 필요한 visited를 생성한다.
  5. DFS 함수 호출
  6. BFS 함수 호출

---

< 회고 >

🤔 💭_

기존에 문제를 풀 때 bfs 방식으로 많이 풀었어서 그런지 dfs 코드는 생각이 잘 나지 않았다.

하지만 더 큰 문제는 .. 알고리즘 문제를 오랜만에 풀다 보니 익숙했던 bfs 코드조차 단번에 확 생각나지 않아서 문제를 풀며 반성했다.

이 문제의 경우 문제에서 dfs/bfs를 구현하라고 되어있었기 때문에 그냥 구현했지만, 앞으로 풀 문제들에서는 알고리즘을 쓰는 데에 대한 이유를 함께 생각하며 풀어야겠다는 생각이 들었다. 분발하자.

 

---

DFS
루트 노드 혹은 임의 노드에서 다음 브랜치로 넘어가기 전에, 해당 브랜치를 모두 탐색하는 방법
(스택 or 재귀 함수를 통해 구현)

• 가능한 한 깊이 내려가면서 탐색을 진행한다.
• 특정 경로를 찾거나, 그래프의 모든 노드를 방문하는 데 유용하다..

def dfs(graph, v, visited):
	visited[v] = True
	for i in graph[v]:
		if not visited[i]:
			dfs(graph, i, visited)
visited = [False] * n
dfs(graph, 1, visited)

---

BFS
루트 노드 혹은 임의 노드에서 인접한 노드부터 먼저 탐색하는 방법

• 인접한 노드를 먼저 탐색한다.
• 최단 경로를 찾는 데 유용하다.

def bfs(graph, start, visited):
	queue = deque([start])
	visited[start] = True
	while queue:
		v = queue.popleft()
		for i in graph[v]:
			if not visited[i]:
				queue.append(i)
				visited[i] = True

---

DFS vs. BFS

	BFS	DFS
	너비 우선 탐색	깊이 우선 탐색
데이터 구조	최단 경로를 찾기 위해 queue 사용	stack 사용
정의	다음 레벨로 이동하기 전에 먼저 동일한 레벨의 모든 노드를 살펴보는 순회 접근 방식	순회가 루트 노드에서 시작하여 근처에 방문하지 않은 노드가 없는 노드에 도달할 때까지 가능한 한 노드를 통해 진행하는 순회 접근 방식
	builds the tree level by level	builds the tree sub-tree by sub-tree
접근 방식	FIFO	LIFO
	더 가까운 정점을 검색하는 데 적합	더 먼 정저메 답이 있을 때 더 적합
활용	최단 경로 찾기, 네트워크 탐색, 그래프의 레벨 순회 등	미로 찾기, 퍼즐 해결, 그래프의 모든 노드를 방문하는 문제 등

 

 

 

 

---

참고

https://www.geeksforgeeks.org/difference-between-bfs-and-dfs/

https://f-lab.kr/insight/understanding-dfs-and-bfs-algorithms-20240517