[BFS / DFS] [백준 / 1260 ] 실버2 - DFS와 BFS (java/자바)

문제

성공

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

public class Main {
    static int N;
    static int M;
    static int V;

    static List<Integer> arr[];
    static boolean[] isVisit;
    static StringBuilder sb;

    public static void main(String[] args) throws IOException {
        BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(r.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        V = Integer.parseInt(st.nextToken());

        arr = new ArrayList[N + 1]; //좌표를 그대로 받아들이기 위해 N+1 사용
        isVisit = new boolean[N + 1];
        sb = new StringBuilder();
        for (int i = 0; i < arr.length; i++) {
            arr[i] = new ArrayList<>();
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(r.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            arr[a].add(b);
            arr[b].add(a);
        }
        for (List<Integer> i : arr) {
            Collections.sort(i);
        }
        dfs(V);
        System.out.println(sb);

        // bfs
        isVisit = new boolean[N + 1];
        sb = new StringBuilder();

        bfs(V);
        System.out.println(sb);

    }

    static void dfs(int index) {
        isVisit[index] = true;
        sb.append(index + " ");
        for (int e : arr[index]) {
            if (!isVisit[e]) {
                dfs(e);
            }
        }
    }
    static void bfs(int index) {
        isVisit[index] = true;
        Queue<Integer> q = new LinkedList<>();
        q.add(index);

        while (!q.isEmpty()) {
            int i = q.poll();
            sb.append(i + " ");
            for (int v : arr[i]) {
                if (!isVisit[v]) {
                    isVisit[v] = true;
                    q.add(v);
                }
            }
        }

    }

}

풀이

예제 입력1을 바탕으로 합니다.

초기화

1. 노드마다 서로 연결되어 있습니다. 이 연결 관계를 표현합니다.

• 1번 노드 = {2, 3}
• 2번 노드 = {4, 1}
• 3번 노드 = {1, 4}
• 4번 노드 = {4, 2}
  
  

2. 문제에서 방문할 수 있는 정점이 여러 개인 경우네는 정점 번호가 작은 것을 먼저 방문할 것을 요구합니다. 따라서 각 코드마다 연결되어 있는 노드들을 오름차순 정렬하여 순서대로 방문하게 합니다.

• 1번 노드 = {2, 3}
• 2번 노드 = {1, 4}
• 3번 노드 = {1, 4}
• 4번 노드 = {2, 4}
  

핵심 로직

3. DFS 그리고 BFS

• DFS :
  V = 1 이므로 1번 노드부터 순회합니다.
  1번 노드를 방문합니다. 1번 노드 방문한 것을 기억합니다. 1번 노드를 가져옵니다. 1번 노드는 2번,3번 노드와 연결 돼 있습니다.
  DFS에 연결 됀 노드 중 방문 안한 첫번째 노드(가장 작은 노드)를 다시 넣습니다. 해당 작업을 반복합니다.

---

• BFS :
  V = 1 이므로 1번 노드부터 순회합니다.
  1번 노드를 방문합니다. 1번 노드 방문한 것을 기억합니다.
  그리고 스택에 쌓습니다.

  이후 스택이 비어있지 않다면
  1번 노드를 가져옵니다. 1번 노드는 2번,3번 노드와 연결 돼 있습니다.
  연결 됀 노드 중 방문 안한 노드들만 스택에 쌓습니다.
  해당 작업을 반복합니다.

  

첫 BFS/DFS 문제 후기

초기화 방법 고민에 시간이 많이 소요 됐다.
초기화부터 잘해야겠다.
알고리즘 난이도는 쉬운문제라 쉬웠었다.
난이도는 초기화 > 알고리즘 이였다.