BFS / DFS 정리

알고리즘 설명

1. BFS
   • BFS는 넓이우선방식으로 그래프를 탐색하는 방법이다. 같은 레벨에 있는 노드들을 탐색한다. 그래서 최단경로를 찾는 탐색방법에 효과적이다.
   • 이를 구현하기 위해 큐를 생성하고 탐색한 노드들을 큐에 담는다. 큐가 빌 때까지 큐에 있는 노드들을 하나씩 꺼내면서 그래프의 범위를 확인하고, 방문 가능한 노드인지 확인한 뒤 탐색을 진행한다.
2. DFS

 

구현

import java.io.*;
import java.util.*;

public class Solution_for_1260 {
    static int N, M, V;
    static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    static boolean[] visited;
    static StringBuilder sb;

    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());

        for (int n = 0; n < N+1; n++) {
            graph.add(new ArrayList<>());
        }

        for (int m = 0; m < M; m++) {
            st = new StringTokenizer(br.readLine());

            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());

            graph.get(start).add(end);
            graph.get(end).add(start);
        }

        // 노드를 오름차순으로 정렬함
        for (int n = 0; n < N+1; n++) {
            Collections.sort(graph.get(n));
        }

        sb = new StringBuilder();
        visited = new boolean[N+1];
        dfs(V);
        System.out.println(sb.toString());

        sb = new StringBuilder();
        visited = new boolean[N+1];
        bfs(V);
        System.out.println(sb.toString());
    }

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

        for (Integer next : graph.get(v)) {
            if (visited[next]) continue;
            dfs(next);
        }
    }

    public static void bfs(int v) {
        Queue<Integer> queue = new LinkedList<>();

        queue.add(v);
        visited[v] = true;

        while (!queue.isEmpty()) {
            Integer curNode = queue.poll();
            sb.append(curNode).append(" ");
            
            for (Integer next : graph.get(curNode)) {
                if (!visited[next]) {
                    visited[next] = true;
                    queue.add(next);
                }
            }
        }
    }
}

[그래프 구현 방법]

1. 인접 행렬
2. 인접 리스트
   자바 언어로 인접 리스트를 구현하기 위해서는 ArrayList<ArrayList<Integer>> graph = new ArrayList<>(); 로 인접 리스트를 생성한 뒤에, 노드의 개수만큼 graph 안에 ArrayList<>를 생성해주어야 한다.
   인접 리스트로 그래프를 구현했을때는 노드들 사이의 이어진 간선들만 표시할 수 있기 때문에 메모리적으로 효율적이다.

ArrayList<ArrayList<Integer>> graph = new ArrayList<>();

for (int n = 0; n < N+1; n++) {
	graph.add(new ArrayList<>());
}

 

 

[방문처리]

 

[DFS 구현]

 

[BFS 구현]

 

관련문제

 

[BFS]

플랫폼	링크	요약	풀이	복습
백준	https://www.acmicpc.net/problem/1260	기본문제 DFS, BFS 모두 구현하는 문제
백준	https://www.acmicpc.net/problem/7576	BFS 탐색, 상태 변화	https://sen-zoo.tistory.com/51	필요

 

[DFS]

플랫폼	링크	요약	풀이	복습
백준	https://www.acmicpc.net/problem/1260	기본문제 DFS, BFS 모두 구현하는 문제