[Algorithm] DFS & BFS 알고리즘

`이것이 코딩 테스트다 (나동빈)` 커리큘럼에 따라 진행합니다

 

✨ DFS

정의

- DFS (깊이 우선 탐색) : 깊은 부분을 우선적으로 탐색하는 알고리즘

- 스택 자료구조 또는 재귀 함수를 이용해 문제를 푼다

동작 과정

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리

2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리

          -> 방문하지 않은 인접 노드가 없을 경우 스택에서 최상단 노드를 꺼낸다

          -> 최상단 노드를 기준으로 깊은 부분을 탐색

3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복

예시

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

graph = [
	[],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

visited = [False] * 9

dfs(graph, 1, visited)

---

✨ BFS

정의

- BFS (너비 우선 탐색) : 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘

- 큐 자료구조를 이용하여 문제를 푼다

- 특정 경로의 최단 경로 문제를 해결하기 위해서도 많이 사용된다

동작 과정

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리

2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리

3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복

예시

from collections import deque

# BFS 메서드
def bfs(graph, start, visited):
	queue = deque([start])
    visited[start] = True
    while queue:
    	v = queue.popleft()
    	print(v, end=' ')
    	for i in graph[v]:
    		if not visited[i]:
        		queue.append(i)
            	visited[i] = True
            
graph = [
	[],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7],
]

visited = [False] * 9
bfs(graph, 1, visited)

---

✨ 문제

1260번: DFS와 BFS

---

✨ 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    static StringBuilder sb = new StringBuilder();
    public static boolean[] visited;
    public static int[][] graph;

    public static int N, M, V;
    public static Queue<Integer> queue = new LinkedList<>();


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken()); // 정점 개수
        M = Integer.parseInt(st.nextToken()); // 간선 개수
        V = Integer.parseInt(st.nextToken()); // 탐색을 시작할 정점 번호

        graph = new int[N+1][N+1];
        visited = new boolean[N+1];

        // 그래프 초기 세팅
        for (int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            graph[x][y] = graph[y][x] = 1;
        }

        dfs(V);
        sb.append("\n");

        // visited 초기화
        visited = new boolean[N+1];
        bfs(V);

        System.out.println(sb);

    }

    public static void dfs(int v) {
        visited[v] = true;
        sb.append(v).append(" ");

        for (int i=1; i<N+1; i++) {
            if (graph[v][i] == 1 && !visited[i]) dfs(i);
        }
    }

    public static void bfs(int v) {
        queue.add(v);
        visited[v] = true;

        while (!queue.isEmpty()) {
            v = queue.poll();
            sb.append(v).append(" ");

            for (int i=1; i<N+1; i++) {
                if (graph[v][i] == 1 && !visited[i]) {
                    queue.add(i);
                    visited[i] = true;
                }
            }
        }
    }
}

// 출처 : https://infodon.tistory.com/96