[BOJ] 1260 DFS와 BFS

DFS와 BFS

풀이

• ArrayList 배열로 구현
• boolean 배열로 방문처리
• 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 라는 조건 때문에 ArrayList 배열 정렬함(Collections.sort 사용)
• StringBuilder 사용해서 출력

코드

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

public class BOJ1260 {
    static ArrayList<Integer>[] nodeList;
    static boolean[] visited;
    static int N, M, V;
    static StringBuilder sb;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        V = Integer.parseInt(st.nextToken())-1;
        nodeList = new ArrayList[N];
        for (int i = 0; i < N; i++)
            nodeList[i] = new ArrayList<>();
        visited = new boolean[N];
        sb = new StringBuilder();
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken()) - 1;
            int B = Integer.parseInt(st.nextToken()) - 1;
            nodeList[A].add(B);
            nodeList[B].add(A);
        }
        for (int i = 0; i < N; i++) {
            Collections.sort(nodeList[i]);
        }

        dfs(V);
        sb.append("\n");
        visited = new boolean[N];

        bfs(V);
        System.out.println(sb);

    }

    private static void bfs(int start) {
        visited[start] = true;
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            sb.append(cur+1).append(" ");
            for (int next : nodeList[cur]) {
                if (!visited[next]) {
                    queue.offer(next);
                    visited[next] = true;
                }
            }
        }
    }

    private static void dfs(int start) {
        visited[start] = true;
        sb.append(start+1).append(" ");
        for (int next : nodeList[start]) {
            if (!visited[next]) {
                dfs(next);
            }
        }
    }
}