[Algorithm] 99클럽 코테 스터디 6일차 TIL BOJ 1260

문제

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

풀이

문제 분석

• 문제에 주어진대로 DFS, BFS를 구현하기만 하면 됐기에 푸는데 어렵지는 않았다

코드

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

public class Main {
    private static boolean[] visited;
    private static boolean[][] graph;
    private static int V, E;
    private static Queue<Integer> queue;

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

        V = Integer.parseInt(token[0]);
        E = Integer.parseInt(token[1]);
        int start = Integer.parseInt(token[2]);
        visited = new boolean[V+1];
        graph = new boolean[V+1][V+1];
        queue = new ArrayDeque<>();

        for(int i=0 ; i<E ; i++) {
            token = br.readLine().split(" ");
            int a = Integer.parseInt(token[0]);
            int b= Integer.parseInt(token[1]);
            graph[a][b] = true;
            graph[b][a] = true;
        }

        reset();
        dfs(start);

        System.out.println();

        reset();
        bfs(start);
    }

    static void dfs(int v) {
        visited[v] = true;
        System.out.print(v+ " ");

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

    static void bfs(int v) {
        queue.add(v);
        visited[v] = true;
        System.out.print(v + " ");

        while(!queue.isEmpty()) {
            v = queue.peek();
            queue.poll();

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

    static void reset() {
        for(int i=1; i<=V; i++) {
            visited[i] = false;
        }
    }
}

TIL

• 다음 영상을 참고하여 DFS와 BFS의 개념을 다시 학습해보았다
  https://www.youtube.com/watch?v=_hxFgg7TLZQ

DFS vs BFS

• 위의 그림은 DFS와 BFS의 차이를 나타낸 것이다
• 깊이 우선 탐색(DFS)는 가장 깊은 곳까지 방문하고, 너비우선탐색(BFS)은 같은 레벨 인접 노드를 전부 방문한다
• DFS는 스택/재귀함수로 구현하고, BFS는 Queue를 통해 구현한다

깊이우선탐색(DFS)

깊이우선탐색 DFS(Depth-Firtst Search)는 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다

• 깊이우선탐색(DFS) 구현 방법

1. 탐색 시작 노드를 스택에 삽입하고 방문을 처리한다
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문을 처리한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다
3. 2번 과정을 더 이상 수행할 수 없을 때까지 방문한다

• 예시
  

1. 시작 노드인 0번을 스택에 담는다
2. 0번 노드를 꺼내 출력하고, 그 인접 노드인 1번 노드를 스택에 담는다
3. 1번 노드를 꺼내 출력하고, 그 인접 노드인 2, 3번 노드를 스택에 담는다
4. 3번 노드를 꺼내 출력하고, 그 인접 노드인 4, 5번 노드를 스택에 담는다
  - 이때 2번 노드는 이미 스택에 추가되었으므로 다시 추가하지 않는다
5. 5번 노드를 꺼내 출력하고, 6, 7번 노드를 스택에 담는다
6. 7번 노드를 꺼내 출력하고, 인접 노드가 없으므로 더 담지 않는다
7. 6번 노드를 꺼내 출력하고, 그 인접 노드인 8번 노드를 스택에 담는다
8. 8번 노드를 꺼내 출력하고, 인접 노드가 없으므로 더 담지 않는다
9. 4번 노드를 꺼내 출력하고, 인접 노드가 이미 스택에 한 번씩 다 들어갔다 나왔으므로 더 담지 않는다
10. 2번 노드를 꺼내 출력하고, 인접 노드가 이미 스택에 한 번씩 다 들어갔다 나왔으므로 더 담지 않는다
11. 더 꺼낼 노드가 없으므로 순회를 종료한다

• 예시의 DFS 경로: 0 > 1 > 3 > 5 > 7 > 6 > 8 > 4 > 2

너비우선탐색(BFS)

너비우선탐색(Breadth-First Search)는 그래프에서 가까운 노드부터 탐색하는 알고리즘이다

• 너비우선탐색(BFS) 구현 방법

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다

• 예시
  

1. 시작 노드인 0번을 스택에 담는다
2. 0번 노드를 꺼내 출력하고, 그 인접 노드를 큐에 담는다
3. 1번 노드를 꺼내 출력하고, 그 인접 노드인 2번 노드와 3번 노드를 큐에 담는다
4. 2번 노드를 꺼내 출력하고, 그 인접 노드인 4번 노드를 큐에 담는다
  - 2번 노드의 인접 노드 중 1, 3번은 이미 큐에 들어갔었으므로 4번 노드만 큐에 담는다
5. 3번 노드를 꺼내 출력하고, 그 인접 노드인 5번 노드를 큐에 담는다
6. 4번 노드를 꺼내 출력하고, 인접 노드가 전부 큐에 담았던 적이 있으므로 다시 담지 않는다
7. 5번 노드를 꺼내 출력하고, 그 인접 노드인 6번과 7번 노드를 큐에 담는다
8. 6번 노드를 꺼내 출력하고, 그 인접 노드인 8번 노드를 큐에 담는다
9. 7번 노드를 꺼내 출력하고, 인접 노드가 없으므로 넘어간다
10. 8번 노드를 꺼내 출력하고, 인접 노드가 없으므로 넘어간다
11. 더 꺼낼 노드가 없으므로 순회를 종료한다

• 예시의 BFS 경로: 0 > 1 > 2 > 3 > 4 > 5 > 6 > 7 > 8