[BOJ 1260] DFS와 BFS JAVA

- 문제

- 풀이

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

public class Main {
    static StringBuilder sb = new StringBuilder();
    static boolean[] visitied;
    static ArrayList<Integer>[] graph;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int start = Integer.parseInt(st.nextToken());

        visitied = new boolean[n + 1];
        graph = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }

        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 = 1; i <= n; i++) {
            Collections.sort(graph[i]);
        }

        dfs(start);
        System.out.println(sb);

        visitied = new boolean[n + 1];
        bfs(start);
    }

    public static void dfs(int node) {
        visitied[node] = true;
        sb.append(node).append(" ");
        for (int next : graph[node]) {
            if (!visitied[next]) {
                dfs(next);
            }
        }
    }

    public static void bfs(int node) {
        Queue<Integer> q = new LinkedList<>();
        q.add(node);
        visitied[node] =true;
        while (!q.isEmpty()) {
            int x = q.poll();
            System.out.print(x+" ");
            for (int y : graph[x]) {
                if(visitied[y] == false) {
                    visitied[y] = true;
                    q.add(y);
                }
            }
        }
    }
}

- 정리

DFS와 BFS 기초에 대해 공부한 후 실전에서 적용시켜 보고싶었다. 그러나 나의 기초 공부가 부족했던 탓인지, 처음에는 매우 헷갈렸다. 처음에는 인접행렬을 만드는 법만 보고와서 인접행렬을 만들고, 이 인접행렬을 토대로 인접리스트를 또 만들었다. 매우 비효율적이였다. 또한Scanner와 메인메서드의 지역변수를 통해 파라미터로 넘기다 보니 중구난방이 되었고, 가독성이 떨어졌다. 그래서 리팩토링한 결과로 이러한 답이 나왔다. BufferReader와 StringTokenizer를 통해 입력받은 것을 잘라주었고, 클래스 내에 static으로 인스턴스 변수를 만들어 주었다. 문제 자체가 BFS/DFS를 동시에 풀도록 하는 것이기 때문에, 동일한 조건을 맞추기 위해서 인스턴스 변수로 만들었다.

그렇게 입력받은 값들을 ArrayList<Integer>[] graph에 담아 저장하도록 했다. 왜 배열로 생성했냐 하면, 각 인덱스가 필요했고, 인덱스에 따른 유동적인 크기를 가진 list를 넣어주고 싶었기 때문이다.

그렇게 작성했고, 각각의 DFS/BFS 로직을 완성했다.

[출처] : 개인저장소