Q. 1260 자바 : DFS와 BFS

Q. 1260 자바 : DFS와 BFS

 

문제 :boj.kr/1260 

실버 2 난이도의 문제이다.

 

그래프가 주어졌을 때 이를 DFS, BFS로 순회하고 결과를 출력하는 문제이다.

주의해야 할 점은 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문

한다는 내용 때문에 그래프를 입력 받은 뒤 정렬이 한번 필요하다.

 

정점이 N, 간선이 M으로 주어지므로 시간복잡도는 아래와 같다.

1. 모든 정점에 대한 정렬 - O(N * M log M)

2. DFS, BFS 순회 - O(2 * N * M)

(ArrayList를 이용한 그래프 탐색의 경우 정점 * 간선 만큼의 시간복잡도를 가짐)

따라서 두 식을 더하면 약 O(N * M) 정도의 시간복잡도를 가진다고 예상할 수 있다.

 

이 문제의 경우 정점의 개수가 최대 1,000개, 간선의 수가 최대 10,000개이므로

시간초과는 걱정하지 않아도 된다.

또한 자료형 역시 int 범위 내에서 모두 해결할 수 있다.

 

풀이는 아래와 같다.

import java.io.*;
import java.lang.reflect.Array;
import java.util.*;

public class Main {
    static FastReader scan = new FastReader();
    static StringBuilder sb = new StringBuilder();

    static int N, M, V;
    static ArrayList<Integer>[] adj;
    static boolean[] visit;

    static void input() {
        
        N = scan.nextInt();
        M = scan.nextInt();
        V = scan.nextInt();
        adj = new ArrayList[N + 1];
        visit = new boolean[N + 1];
        for (int i = 1;i <= N; i++)
            adj[i] = new ArrayList<>();

        for (int i = 1; i <= M; i++){
            int s = scan.nextInt();
            int e = scan.nextInt();
            adj[s].add(e);
            adj[e].add(s);
        }

    }

    static void dfs(int x) {
        
        visit[x] = true;
        sb.append(x).append(' ');
        for (int y: adj[x]) {
            if (!visit[y]) dfs(y);
        }
    }

    static void bfs(int start) {

        Queue<Integer> que = new LinkedList<>();
        visit[start] = true;
        que.add(start);

        while (!que.isEmpty()) {
            int x = que.poll();
            sb.append(x).append(' ');
            for (int y: adj[x]) {
                if (!visit[y]) {
                    que.add(y);
                    visit[y] = true;
                }
            }
        }
    }

    static void pro() {

        for (int i = 1; i <= N; i++)
            Collections.sort(adj[i]);

        dfs(V);
        for (int i = 1; i <= N; i++) visit[i] = false;
        sb.append('\n');
        bfs(V);

        System.out.println(sb);
    }

    public static void main(String[] args) {
        input();
        pro();
    }


    static class FastReader {
    	// BufferedReader의 빠른 속도, 
        // + Scanner의 타입별 입력값을 받는 기능을 혼합
        // (자바 내부에 구현된 Scanner는 속도가 느림)
        // 다른분의 코드를 참고한 코드
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws FileNotFoundException {
            br = new BufferedReader(new FileReader(new File(s)));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

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

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}