Q. 5567 자바 : 결혼식

Q. 5567 자바 : 결혼식

 

문제 : boj.kr/5567

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

 

간선이 주어지고 탐색을 통해 깊이가 2인 정점까지 방문 가능하다면 몇 개의 정점을 방문 가능한지 세는 문제이다.

(상근이의 친구 - 깊이가 1, 친구의 친구 - 깊이가 2)

 

간선만 주어지므로 격자형 그래프가 아니라 ArrayList를 사용해서 문제를 해결했다.

또한 양방향 그래프이므로 간선을 입력받을 때 두 정점 모두 표시했다.

 

이 문제의 경우 아래와 같은 방식으로 해결했다.

1. 입력값을 받아 두 정점에 저장한다.

2. 깊이우선탐색(DFS)를 시작한다.

3. 이 때 주의해야 할 점은 깊이가 2일 때 까지 모든 정점을 탐색해야 하므로  방문 여부 확인은 하되, 이미 방문한 정점에 대해서도 탐색한다.

(어떤 사람에게는 친구의 친구이지만, 다른 사람에게는 친구일 수 있다.)

 

이 문제의 경우 정점 n이 최대 500개, 간선m이  최대 10,000개이다.

리스트를 사용한 일반 그래프의 시간복잡도는 O(n + m)으로 시간초과는 걱정하지 않아도 된다.

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

 

풀이는 아래와 같다.

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


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

    static int M, N, cnt = -1;
    static List<Integer>[] list;
    static boolean[] visit;

    static int[] dy = {0, 1, 0, -1};
    static int[] dx = {1, 0, -1, 0};

    static void input() {

        N = scan.nextInt();
        M = scan.nextInt();
        list = new List[N + 1];
        visit = new boolean[N + 1];

        for (int i = 1; i <= N; i++) {
            list[i] = new LinkedList<>();
        }

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

    static void dfs(int start, int depth) {
        
        if (!visit[start]) {
            visit[start] = true;
            cnt++;
        }
        if (depth == 2) return;
        
        for (int end: list[start]) {
            dfs(end, depth + 1);
        }
    }

    static void pro() {

        dfs(1, 0);
        System.out.println(cnt);
    }

    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;
        }
    }
}