[Java] DFS BFS 기본 (DFS와 BFS)

 

자바로 처음 풀어본 알고리즘 문제.

알고리즘을 너무 오랜만에 풀어봐서 감을 익히려고 알고리즘 근본 문제인 dfs, bfs를 풀어봤다.

자바는 그동안 사용했던 파이썬과 다른 점이 매우 많은 것 같다.

파이썬이 얼마나 선녀였던지 알 수 있었지만 학기 내내 사용하던 로우레벨 언어 C와 비교하면 자바 또한 선녀였다.

C를 사용했던 덕분에 queue와 linkedlist, sort를 직접 구현하지 않고 라이브러리를 이용할 수 있다는 것이 얼마나 편한 것인지 알았다.

 

 

 

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

1260번: DFS와 BFS

 

dfs와 bfs 코드가 확실히 파이썬에 비해서는 매우 복잡하지만 C에 비해서는 간결하다고 할 수 있다.

 

자바에서 입력은 BufferedReader를 사용한다. 기존에 사용하던 scanner는 BufferedReader에 비해서 속도가 느려서 사용하지 않는다고 함. 

 

BufferedReader는 줄 단위로 읽어 오기 때문에 StringTokenizer를 이용해 공백을 기준으로 단어를 나눈다.

 

자바에서 String은 하나의 불변 객체이므로 str1 + str2를 한다면 또 하나의 객체 str3을 생성하게 된다. 따라서 이러한 연산이 많아진다면 프로그램 성능이 떨어지게 된다.

StringBuilder는 새로운 객체를 생성하는 것이 아니라 기존의 데이터를 더하는 방식이기 때문에 속도와 성능 측면에서 더욱 우수하다.

 

자바는 내부적으로 int 배열은 Quick sort를, object 배열은 merge sort (stable 하기 때문에)를 사용한다.

 

 

 

 

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

public class Main {

    static int N, M, V; //정점 개수, 간선 개수, 시작 정점
    static ArrayList<Integer> graph[];
    static boolean[] visited1, visited2;
    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());
        sb = new StringBuilder();

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        V = Integer.parseInt(st.nextToken());


        graph = new ArrayList[N+1];
        for(int i=0; i<graph.length; i++){
            graph[i] = new ArrayList<>();
        }
        visited1 = new boolean[N+1];
        visited2 = new boolean[N+1];

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

            graph[a].add(b);
            graph[b].add(a);
        }

        for(int i=0; i<graph.length; i++){
            Collections.sort(graph[i]);
        }

        dfs(V);
        sb.append("\n");
        bfs(V);
        System.out.println(sb);

    }

    public static void dfs(int v){
        visited1[v] = true;
        sb.append(v + " ");

        for(int i : graph[v]){
            if(!visited1[i]){
                dfs(i);
            }
        }
    }

    public static void bfs(int start){
        visited2[start] = true;
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);

        while(!queue.isEmpty()){
            int v = queue.poll();
            sb.append(v + " ");

            for(int i: graph[v]){
                if(!visited2[i]){
                    queue.add(i);
                    visited2[i]= true;
                }
            }
        }
    }

}