코드트리 [자바 java] 그래프 탐색

https://www.codetree.ai/missions/2/problems/graph-traversal/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

정점과 간선이 주어지고, 1에서 출발해서 도착할 수 있는 정점을 구하는 문제이다.

처음에는 유니온파인드로 풀어야하나 했지만, 생각해보니 dfs로 탐색하고, 방문한 수로 같은 그래프에 해당하는 정점의 갯수를 구하는게 더 빨랐다.

리스트를 이용해서 각 정점과 연결되어있는 정점들을 저장했고, 1번리스트에 있는 정점들부터 stack에 차례로 쌓으면서 dfs를 수행했다.

 

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




public class Main {

    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());

        List<Integer>[] list = new LinkedList[n+1];

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

        for(int i = 0;i<m;i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            list[a].add(b);
            list[b].add(a);
        }

        Stack<Integer> stack = new Stack<>();

        for(int i = 0;i<list[1].size();i++){
            stack.push(list[1].get(i));
        }

        boolean[] vis = new boolean[n+1];
        vis[1] = true;

        while(stack.isEmpty() != true){
            int k = stack.pop();
            if(vis[k] == false){
                vis[k] = true;
                for(int i = 0;i<list[k].size();i++){
                    int g = list[k].get(i);
                    if(vis[g] == false){
                        stack.push(g);
                    }
                }
            }

        }

        int cnt = 0;
        for(int i = 2;i<=n;i++){
            
            if(vis[i] == true) {
                cnt++;
            }
        }

        System.out.println(cnt);

    }
}