๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ
์•Œ๊ณ ๋ฆฌ์ฆ˜

[Java] BOJ 1260 DFS์™€ BFS

by ๐ŸŠ๊ทค๐ŸŠ 2024. 8. 1.

๋ฌธ์ œ 

๋ฌธ์ œ ๋งํฌ https://www.acmicpc.net/problem/1260

  • ๊ทธ๋ž˜ํ”„๋ฅผ DFS๋กœ ํƒ์ƒ‰ํ•œ ๊ฒฐ๊ณผ์™€ BFS๋กœ ํƒ์ƒ‰ํ•œ ๊ฒฐ๊ณผ๋ฅผ ์ถœ๋ ฅํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค.
  • ๋‹จ, ๋ฐฉ๋ฌธํ•  ์ˆ˜ ์žˆ๋Š” ์ •์ ์ด ์—ฌ๋Ÿฌ ๊ฐœ์ธ ๊ฒฝ์šฐ์—๋Š” ์ •์  ๋ฒˆํ˜ธ๊ฐ€ ์ž‘์€ ๊ฒƒ์„ ๋จผ์ € ๋ฐฉ๋ฌธํ•˜๊ณ , ๋” ์ด์ƒ ๋ฐฉ๋ฌธํ•  ์ˆ˜ ์žˆ๋Š” ์ ์ด ์—†๋Š” ๊ฒฝ์šฐ ์ข…๋ฃŒํ•œ๋‹ค. ์ •์  ๋ฒˆํ˜ธ๋Š” 1๋ฒˆ๋ถ€ํ„ฐ N๋ฒˆ๊นŒ์ง€์ด๋‹ค.
  • ์ฒซ์งธ ์ค„์— ์ •์ ์˜ ๊ฐœ์ˆ˜ N(1 ≤ N ≤ 1,000), ๊ฐ„์„ ์˜ ๊ฐœ์ˆ˜ M(1 ≤ M ≤ 10,000), ํƒ์ƒ‰์„ ์‹œ์ž‘ํ•  ์ •์ ์˜ ๋ฒˆํ˜ธ V๊ฐ€ ์ฃผ์–ด์ง„๋‹ค.
  • ๋‹ค์Œ M๊ฐœ์˜ ์ค„์—๋Š” ๊ฐ„์„ ์ด ์—ฐ๊ฒฐํ•˜๋Š” ๋‘ ์ •์ ์˜ ๋ฒˆํ˜ธ๊ฐ€ ์ฃผ์–ด์ง„๋‹ค.
  • ์–ด๋–ค ๋‘ ์ •์  ์‚ฌ์ด์— ์—ฌ๋Ÿฌ ๊ฐœ์˜ ๊ฐ„์„ ์ด ์žˆ์„ ์ˆ˜ ์žˆ๋‹ค.
  • ์ž…๋ ฅ์œผ๋กœ ์ฃผ์–ด์ง€๋Š” ๊ฐ„์„ ์€ ์–‘๋ฐฉํ–ฅ์ด๋‹ค.
  • ์ฒซ์งธ ์ค„์— DFS๋ฅผ ์ˆ˜ํ–‰ํ•œ ๊ฒฐ๊ณผ๋ฅผ, ๊ทธ ๋‹ค์Œ ์ค„์—๋Š” BFS๋ฅผ ์ˆ˜ํ–‰ํ•œ ๊ฒฐ๊ณผ๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค. V๋ถ€ํ„ฐ ๋ฐฉ๋ฌธ๋œ ์ ์„ ์ˆœ์„œ๋Œ€๋กœ ์ถœ๋ ฅํ•˜๋ฉด ๋œ๋‹ค.

์•„์ด๋””์–ด

  • ์šฐ์„  ์—ฐ๊ฒฐ ๋…ธ๋“œ๋ฅผ ์„œ๋กœ ๊ธฐ๋กํ•˜๊ธฐ ์œ„ํ•ด TreeSet ๋ฐฐ์—ด์„ N + 1ํฌ๊ธฐ๋กœ ์„ ์–ธํ–ˆ๋‹ค.
  • TreeSet์œผ๋กœ ๋ฐฐ์—ด์„ ์„ ์–ธํ•œ ์ด์œ ๋Š” ๋ฐฉ๋ฌธํ•  ์ˆ˜ ์žˆ๋Š” ์ •์ ์ด ์—ฌ๋Ÿฌ๊ฐœ์ผ๋•Œ, ์ •์  ๋ฒˆํ˜ธ๊ฐ€ ์ž‘์€ ๊ฒƒ์„ ๋จผ์ € ๋ฐฉ๋ฌธํ•œ๋‹ค๊ณ  ํ•˜์˜€์œผ๋ฏ€๋กœ ์˜ค๋ฆ„์ฐจ์ˆœ ์ •๋ ฌ์„ ํ•˜๊ธฐ์œ„ํ•ด TreeSet์„ ์ผ๋‹ค.
  • ๊ทธ๋ฆฌ๊ณ  DFS์™€ BFS์˜ ๊ฒฐ๊ณผ๊ฐ’์„ ์ €์žฅํ•˜๊ธฐ ์œ„ํ•ด ArrayList๋ฅผ ์„ ์–ธํ•˜๊ณ , ๊ฐ ๋…ธ๋“œ์˜ ๋ฐฉ๋ฌธ์ฒ˜๋ฆฌ๋ฅผ ์œ„ํ•ด N + 1 ํฌ๊ธฐ์˜ boolean ๋ฐฐ์—ด์„ ์„ ์–ธํ–ˆ๋‹ค.
  • ๋จผ์ € DFS๋ฅผ ์‹œ์ž‘ ์ •์ ์ธ V๋ถ€ํ„ฐ ๋Œ๋ฆฌ๊ธฐ์ „, ๊ฒฐ๊ณผ๊ฐ’ ArrayList์— ์ €์žฅํ•˜๊ณ  ๋ฐฉ๋ฌธ์ฒ˜๋ฆฌ๋ฅผ ํ•ด์ค€๋‹ค. 
  • ๊ทธ๋ฆฌ๊ณ  DFS๋ฅผ V๋ถ€ํ„ฐ ๋Œ๋ฆฌ๋ฉด์„œ ๊ธฐ์กด ๋…ธ๋“œ์— ์—ฐ๊ฒฐ๋˜์–ด ์žˆ๋˜ ๋…ธ๋“œ๋ฒˆํ˜ธ์ค‘์— ๋งŒ์•ฝ ๋ฐฉ๋ฌธํ•˜์ง€ ์•Š์€ ๋…ธ๋“œ๊ฐ€ ์žˆ๋‹ค๋ฉด ๋ฐฉ๋ฌธ์ฒ˜๋ฆฌ๋ฅผ ํ•ด์ฃผ๊ณ  ๊ฒฐ๊ณผ๊ฐ’ ArrayList์— ์ €์žฅํ•ด์ค€๋‹ค. 
  • ๊ทธ๋ฆฌ๊ณ  ํ•ด๋‹น ๋…ธ๋“œ ๋ฒˆํ˜ธ๋กœ ๋‹ค์‹œ DFS๋ฅผ ๋Œ๋ฆฐ๋‹ค. (DFS๋Š” ๊นŠ์ด ์šฐ์„  ํƒ์ƒ‰ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๊ธฐ ๋•Œ๋ฌธ)
  • DFS๋ฅผ ๋Œ๋ฆฌ๋‹ค๊ฐ€ ๊ฒฐ๊ณผ๊ฐ’ ArrayList์˜ ํฌ๊ธฐ๊ฐ€ ๋…ธ๋“œ ๊ฐœ์ˆ˜์™€ ๊ฐ™๋‹ค๋ฉด DFS๋ฅผ ์ข…๋ฃŒํ•œ๋‹ค.
  • DFS๋ฅผ ์ข…๋ฃŒํ•˜๊ณ  ๋ฐฉ๋ฌธ ์—ฌ๋ถ€๋ฅผ ์ €์žฅํ•˜๋Š” boolean ๋ฐฐ์—ด์„ ์ดˆ๊ธฐํ™” ์‹œ์ผœ์ค€ ๋’ค, BFS๋ฅผ ๋Œ๋ฆฐ๋‹ค.
  • ๋งˆ์ฐฌ๊ฐ€์ง€๋กœ BFS๋„ ์‹œ์ž‘ ๋…ธ๋“œ V๋ถ€ํ„ฐ ์‹œ์ž‘ํ•˜๊ณ  ์ดˆ๊ธฐ ๋…ธ๋“œ๊ฐ’์„ BFS ๊ฒฐ๊ณผ๊ฐ’์„ ์ €์žฅํ•˜๋Š” ArrayList์— ์ €์žฅํ•˜๊ณ  ํ•ด๋‹น ๋…ธ๋“œ๋ฅผ ๋ฐฉ๋ฌธ์ฒ˜๋ฆฌ ํ•ด์ค€๋’ค, Queue์— ๋„ฃ๋Š”๋‹ค.
  • ๊ทธ๋ฆฌ๊ณ  Queue๊ฐ€ ๋นŒ๋•Œ๊นŒ์ง€ while๋ฌธ์„ ๋Œ๋ฆฌ๋Š”๋ฐ, while๋ฌธ ์•ˆ์—์„œ Queue์— ๋“ค์–ด์žˆ๋Š” ๊ฐ’์„ ๋นผ์„œ ์ƒˆ๋กœ์šด ๋ณ€์ˆ˜์— ์ €์žฅํ•˜๊ณ  ๊ทธ ๋ณ€์ˆ˜๋ฅผ ๊ธฐ์ค€์œผ๋กœ for๋ฌธ์„ ํ†ตํ•ด ์—ฐ๊ฒฐ๋˜์–ด ์žˆ๋Š” ๋…ธ๋“œ์ค‘์— ๋ฐฉ๋ฌธํ•˜์ง€ ์•Š์€ ๊ฒƒ์ด ์žˆ๋‹ค๋ฉด ํ•ด๋‹น ๋…ธ๋“œ๋ฅผ Queue์— ๋„ฃ์–ด๋‘๊ณ ,  ๋ฐฉ๋ฌธ์ฒ˜์น˜๋ฅผ ํ•ด์ค€ ๋’ค, ๊ฒฐ๊ณผ๊ฐ’ ArrayList์— ์ €์žฅํ•œ๋‹ค.
  • for๋ฌธ์œผ๋กœ ๊ธฐ์กด ๋…ธ๋“œ์— ์—ฐ๊ฒฐ๋˜์–ด์žˆ๋˜ ๋…ธ๋“œ๋“ค์„ ๋ชจ๋‘ ๋ฐฉ๋ฌธํ–ˆ๋‹ค๋ฉด ์ƒˆ๋กญ๊ฒŒ Queue์— ๋„ฃ์–ด์ง„ ๋…ธ๋“œ ๊ฐ’๋“ค์„ ๊ธฐ์ค€์œผ๋กœ ๋‹ค์‹œ for๋ฌธ์„ ๋Œ๋ฆฐ๋‹ค.
  • ์ตœ์ข…์ ์œผ๋กœ ๋ชจ๋“  ๋…ธ๋“œ๋ฅผ ๋ฐฉ๋ฌธํ–ˆ๋‹ค๋ฉด ๋” ์ด์ƒ Queue์— ๋‚จ์•„์žˆ๋Š” ๋…ธ๋“œ๊ฐ€ ์—†๊ธฐ ๋•Œ๋ฌธ์— while๋ฌธ์ด ์ข…๋ฃŒ๋œ๋‹ค.

๊ฒช์€ ์‹œํ–‰์ฐฉ์˜ค

  • ์‚ฌ์‹ค BFS๋Š” ๊ทธ๋‚˜๋งˆ ์‰ฝ๊ฒŒ ํ’€์—ˆ๋˜ ๊ฒƒ ๊ฐ™์€๋ฐ... DFS๊ฐ€ ๋„ˆ๋ฌด ์˜ค๋žœ๋งŒ์ด๋‹ค ๋ณด๋‹ˆ ๋ฐฉ๋ฒ•์ด ์ƒ๊ฐ์ด ์•ˆ๋‚˜์„œ ์กฐ๊ธˆ ์˜ค๋ž˜ ๊ณ ๋ฏผํ–ˆ๋˜ ๊ฒƒ ๊ฐ™๋‹ค.
  • ๊ทธ๋ฆฌ๊ณ  ๊ณ„์† DFS ๊ฒฐ๊ณผ๊ฐ’ ๋‚˜์˜ค๋Š”๊ฒŒ ์ด์ƒํ•ด์„œ ๋ญ๊ฐ€ ๋ฌธ์ œ์ธ์ง€ ๋ณด๋‹ˆ๊นŒ ๊ฒฐ๊ณผ๊ฐ’ ์ €์žฅ์„ DFS๋ฅผ ๋Œ๋ฆฌ๊ณ  ๋‚˜์„œ ํ•˜๊ณ  ์žˆ๋Š” ๊ฒƒ์ด์˜€๋‹ค...ใ…‹ใ…‹ใ…‹......์‚ฌ์†Œํ•œ ๊ฒƒ์ด๊ธด ํ•˜์ง€๋งŒ... ๊ทธ๋ž˜๋„ ์ฃผ์˜ํ•ด์„œ ํ’€์–ด์•ผ๊ฒ ๋‹ค...

ํž˜๋“  ์‹ธ์›€์ด์˜€๋‹ค.... ๊ทธ๋ž˜๋„ ์ด ๊ธฐํšŒ์— DFS, BFS ํ™•์‹คํžˆ ์ดํ•ดํ•˜๊ณ  ๋„˜์–ด๊ฐ€๋Š” ๊ฒƒ ๊ฐ™์•„์„œ ๋ฟŒ๋“ฏํ–ˆ๋‹ค!

์ฝ”๋“œ

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

public class BOJ1260 {

    static TreeSet<Integer>[] arr;

    static ArrayList<Integer> d_result;

    static ArrayList<Integer> b_result;

    static boolean visited[];

    static int N;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        StringTokenizer st = new StringTokenizer(br.readLine());

        // ์ •์ ์˜ ๊ฐœ์ˆ˜
        N = Integer.parseInt(st.nextToken());

        // ๊ฐ„์„ ์˜ ๊ฐœ์ˆ˜
        int M = Integer.parseInt(st.nextToken());

        // ์‹œ์ž‘ํ•  ์ •์ ์˜ ๋ฒˆํ˜ธ
        int V = Integer.parseInt(st.nextToken());

        // ์—ฐ๊ฒฐ ์ •๋ณด๋ฅผ ์ €์žฅํ•  ArrayList ๋ฐฐ์—ด
        arr = new TreeSet[N + 1];

        // dfs ๊ฒฐ๊ณผ๊ฐ’ ์ €์žฅํ•  ArrayList
        d_result = new ArrayList<>();

        // bfs ๊ฒฐ๊ณผ๊ฐ’ ์ €์žฅํ•  ArrayList
        b_result = new ArrayList<>();

        // ๋…ธ๋“œ์˜ ๋ฐฉ๋ฌธ์—ฌ๋ถ€๋ฅผ ์ €์žฅํ•  ๋ฐฐ์—ด
        visited = new boolean[N + 1];

        for(int i = 1; i <= N; i++){
            // ๋ฐฐ์—ด ์›์†Œ๋ฅผ TreeSet์œผ๋กœ ์ดˆ๊ธฐํ™”
            arr[i] = new TreeSet<Integer>();
        }

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

            int n1 = Integer.parseInt(st2.nextToken());
            int n2 = Integer.parseInt(st2.nextToken());

            // ๊ฐ ๋…ธ๋“œ์— ์—ฐ๊ฒฐ๋œ ๋…ธ๋“œ ์ถ”๊ฐ€
            arr[n1].add(n2);
            arr[n2].add(n1);
        }

        // DFS์˜ ๊ฒฐ๊ณผ๊ฐ’์„ ์ €์žฅํ•  ArrayList์— ์ดˆ๊ธฐ ๋…ธ๋“œ๊ฐ’์„ ์ €์žฅ
        d_result.add(V);

        // ์ดˆ๊ธฐ ๋…ธ๋“œ์˜ ๋ฐฉ๋ฌธ๊ฐ’์„ true๋กœ ๋ณ€ํ™˜
        visited[V] = true;

        // DFS๋ฅผ ๋Œ๋ฆผ
        DFS(V);

        // BFs๋ฅผ ๋Œ๋ฆฌ๊ธฐ์ „ ๋ฐฉ๋ฌธ์—ฌ๋ถ€๋ฅผ ์ดˆ๊ธฐํ™”
        visited = new boolean[N + 1];

        // BFS๋ฅผ ๋Œ๋ฆผ
        BFS(V);

        // DFS ๊ฒฐ๊ณผ๊ฐ’ ์ถœ๋ ฅ
        for(int i = 0; i < d_result.size(); i++){
            sb.append(d_result.get(i) + " ");
        }

        sb.append("\n");

        // BFS ๊ฒฐ๊ณผ๊ฐ’ ์ถœ๋ ฅ
        for(int i = 0; i < b_result.size(); i++){
            sb.append(b_result.get(i) + " ");
        }

        System.out.println(sb);
    }

    static public void DFS(int a){
        // ๋งŒ์•ฝ DFS์˜ ๊ฒฐ๊ณผ๊ฐ’ ArrayList์˜ ํฌ๊ธฐ๊ฐ€ ๋…ธ๋“œ ๊ฐœ์ˆ˜์™€ ๊ฐ™๋‹ค๋ฉด
        if(d_result.size() == N){
            return;
        }

        // ๊ธฐ์กด ๋…ธ๋“œ์— ์—ฐ๊ฒฐ๋˜์–ด ์žˆ๋Š” ๋…ธ๋“œ์ค‘
        for(int i : arr[a]){
            // ๋งŒ์•ฝ ํ•ด๋‹น ๋…ธ๋“œ๋ฅผ ๋ฐฉ๋ฌธํ•˜์ง€ ์•Š์•˜๋‹ค๋ฉด
            if(!visited[i]){
                // ํ•ด๋‹น ๋…ธ๋“œ์˜ ๊ฒฐ๊ณผ๊ฐ’์„ true๋กœ ๋ฐ”๊พธ๊ณ 
                visited[i] = true;

                // ๊ทธ๋ฆฌ๊ณ  DFS ๊ฒฐ๊ณผ๊ฐ’ ArrayList์— ํ•ด๋‹น ๋…ธ๋“œ๋ฅผ ๋„ฃ์Œ
                d_result.add(i);

                // ํ•ด๋‹น ๋…ธ๋“œ๋ฅผ ๊ธฐ์ค€์œผ๋กœ ๋‹ค์‹œ DFS๋ฅผ ๋Œ๋ฆผ
                DFS(i);
            }
        }
    }

    static public void BFS(int a){
        Queue<Integer> q = new LinkedList<>();

        // ์ดˆ๊ธฐ ๋…ธ๋“œ๊ฐ’์„ Queue์— ๋„ฃ๊ณ 
        q.offer(a);

        // bfs ๊ฒฐ๊ณผ๊ฐ’ ArrayList์— ํ•ด๋‹น ๋…ธ๋“œ๊ฐ’ ์ €์žฅ
        b_result.add(a);

        // ๊ทธ๋ฆฌ๊ณ  ํ•ด๋‹น ๋…ธ๋“œ๋ฅผ ๋ฐฉ๋ฌธ์ฒ˜๋ฆฌ
        visited[a] = true;

        while(!q.isEmpty()){
            int node = q.poll();

            // ํ•ด๋‹น ๋…ธ๋“œ์— ์žˆ๋Š” ๊ฐ’๋“ค ์ค‘
            for(int i: arr[node]){
                // ๋ฐฉ๋ฌธํ•˜์ง€ ์•Š์€ ๋…ธ๋“œ๊ฐ€ ์žˆ๋‹ค๋ฉด
                if(!visited[i]){
                    // ํ•ด๋‹น ๋…ธ๋“œ ๋ฒˆํ˜ธ๋ฅผ Queue์— ๋„ฃ์–ด์ฃผ๊ณ 
                    q.offer(i);

                    // ๋ฐฉ๋ฌธ์ฒ˜๋ฆฌ๋ฅผ ํ•ด์คŒ
                    visited[i] = true;

                    // ๊ทธ๋ฆฌ๊ณ  bfs ๊ฒฐ๊ณผ๊ฐ’ ArrayList์— ํ•ด๋‹น ๋…ธ๋“œ ์ €์žฅ
                    b_result.add(i);
                }
            }
        }
    }
}