[PS] DFS와 BFS (백준 1260번)

이전에 풀어본 정말 간단한 DFS/BFS 예제인데, java로 변수명이랑 객체지향 개념을 녹아내려니까 굉장히 오래 걸리고, 풀이 또한 길었다.

java로 코테를 볼 때는 최대한 시간 안에 빠르게 문제를 푼 다음, 리팩토링을 하는 방향으로 진행하자.

아직 너무나도 부족해서, 시간이 많이 부족하다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Deque;
import java.util.StringTokenizer;

/* BOJ no.1260 - DFS와 BFS (DFS BFS) */
public class Main {

    
    static int NUMBER_OF_VERTEX, NUMBER_OF_EDGE, START_VERTEX;
    static ArrayList<Integer>[] connectedEdges;
    static StringBuffer stringBuffer;
    static boolean[] isVisit;
    
    public static void main(String[] args) {
        input();
        process();
        printOfResult();
    }

    static void input() {
        Reader reader = new Reader();
        NUMBER_OF_VERTEX = reader.nextInt();
        NUMBER_OF_EDGE = reader.nextInt();
        START_VERTEX = reader.nextInt();
        
        int LIMIT_OF_EDGE = NUMBER_OF_EDGE + 1;
        int LIMIT_OF_VERTEX = NUMBER_OF_VERTEX + 1;

        isVisit = new boolean[LIMIT_OF_VERTEX];
        stringBuffer = new StringBuffer(NUMBER_OF_VERTEX * 3);
        connectedEdges = new ArrayList[LIMIT_OF_VERTEX];
        for (int idx = 1; idx < LIMIT_OF_VERTEX; idx++) {
            connectedEdges[idx] = new ArrayList<>(LIMIT_OF_VERTEX);
        }
        
        for (int idx = 0; idx < NUMBER_OF_EDGE; idx++) {
            int firstNode = reader.nextInt();
            int secondNode = reader.nextInt();
            connectedEdges[firstNode].add(secondNode);
            connectedEdges[secondNode].add(firstNode);
        }

        for (int idx = 1; idx < LIMIT_OF_VERTEX; idx++) {
            Collections.sort(connectedEdges[idx]);
        }
    }

    static void process() {
        dfs(START_VERTEX);
        Arrays.fill(isVisit, false);
        stringBuffer.append("\n");
        bfs();
    }

    static void dfs(int node) {
        isVisit[node] = true;
        stringBuffer.append(String.valueOf(node));
        stringBuffer.append(" ");
        
        for (int nextNode : connectedEdges[node]) {
            if (!isVisit[nextNode]) dfs(nextNode);
        }
    }

    static void bfs() {
        Deque<Integer> queue = new ArrayDeque<>(NUMBER_OF_EDGE);
        
        queue.add(START_VERTEX);
        isVisit[START_VERTEX] = true;
        int node = -1;
        while (!queue.isEmpty()) {
            node = queue.pop();
            stringBuffer.append(String.valueOf(node));
            stringBuffer.append(" ");
            for (int nextNode : connectedEdges[node]) {
                if (!isVisit[nextNode]) {
                    queue.add(nextNode);
                    isVisit[nextNode] = true;
                }
            }
        }
    }

    static void printOfResult() {
        System.out.println(stringBuffer.toString());
    }
    
    static class Reader {
        BufferedReader bufferedReader;
        StringTokenizer stringTokenizer;

        Reader() {
            bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        }
        
        String next() {
            while (stringTokenizer == null || !stringTokenizer.hasMoreElements()) {
                try {
                    stringTokenizer = new StringTokenizer(bufferedReader.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return stringTokenizer.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

부족한 점이나 피드백은 사랑입니다 :)