백준 1260번) DFS와 BFS java

분석

---

이 문제를 풀려면 bfs와 dfs에 대해서 먼저 알아야한다.

 

dfs, bfs는 그래프를 탐색할 때 사용하는 알고리즘인데, 구현 방식이 다르므로 목적에 따라 다른 알고리즘이 사용된다.

(*그래프 : 노드와 간선으로 이루어진 자료구조의 일종)

 

깊이 우선 탐색(bfs)

- 루트 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완전하게 탐색하는 방식을 말한다.

  스택 , 재귀함수로 구현이 가능하지만 재귀함수로 구현하면 좀 더 간략한 코드가 나온다.

  모든 노드를 방문해야하거나 , 그래프가 큰 경우 사용

 

너비 우선 탐색(bfs)

- 인접한 노드를 먼저 탐색하는 방식을 말한다. 

  가까운 노드를 먼저 방문하고 멀리있는 노드를 나중에 방문한다.

  큐로 구현할 수 있다.

  최단 경로를 구할 경우 사용

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static StringBuilder sb = new StringBuilder();
    static int node, line, start;
    static int[][] arr;
    static boolean[] visit;

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        node = Integer.parseInt(st.nextToken());
        line = Integer.parseInt(st.nextToken());
        start = Integer.parseInt(st.nextToken());

        visit = new boolean[node + 1];
        arr = new int[node + 1][node + 1];

        for (int i = 0; i < line; i++) {
            StringTokenizer str  = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(str.nextToken());
            int b = Integer.parseInt(str.nextToken());
            arr[a][b] = arr[b][a] = 1;
        }


        dfs(start);
        visit = new boolean[node + 1];
        sb.append("\n");
        bfs(start);
        System.out.println(sb);
    }

    static void dfs(int start) {
        sb.append(start + " ");
        visit[start] = true;
        for (int i = 1; i <= node; i++) {
            if (arr[start][i] == 1 && !visit[i]) {
                dfs(i);
            }
        }
    }

    static void bfs(int start) {
        Queue<Integer> q = new LinkedList<>();

        q.add(start);
        visit[start] = true;

        while(!q.isEmpty()){
            int value = q.poll();
            sb.append(value+" ");

            for(int i=1;i<=node;i++){
                if(arr[value][i] == 1 && !visit[i]){
                    visit[i] = true;
                    q.add(i);
                }
            }

        }
    }


}