[백준] 9372 상근이의 여행 - 그래프 + DFS JAVA

https://www.acmicpc.net/problem/9372

코드설명

그래프문제에 DFS를 활용하여 모든 국가를 방문하면됩니다.

 

일반적인 그래프 알고리즘과 DFS를 활용하여 진행한다면 풀수 있습니다.

 

코드

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

public class Main {
	public static int T, N, M;
	public static int[] arr;
	public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
	public static boolean[] visited;
	public static int answer = 0;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine()); 	
    	
    	T = Integer.parseInt(st.nextToken());
    	
    	for(int i=0;i<T;i++) {
    		st = new StringTokenizer(br.readLine());
    		N = Integer.parseInt(st.nextToken());
    		M = Integer.parseInt(st.nextToken());
    		
    		
    		graph = new ArrayList<ArrayList<Integer>>();
    		for(int j=0;j<=N;j++) {
    			graph.add(new ArrayList<>());
    		}
    		
    		visited = new boolean[N+1];
    		
    		for(int j=0;j<M;j++) {
    			st = new StringTokenizer(br.readLine());
        		int a = Integer.parseInt(st.nextToken());
        		int b = Integer.parseInt(st.nextToken());
        		graph.get(a).add(b);
        		graph.get(b).add(a);
    		}
    		
    		answer = 0;
    		visited[1] = true;
    		simulate(1);
    		System.out.println(answer);
    	}

    	
    }
    
    public static void simulate(int start) {
    	
    	boolean Flag = false;
    	for(int i=1;i<=N; i++) {
    		if(visited[i] == false) {
    			Flag = true;
    		}
    	}
    	
    	if(Flag == false)
    		return ;
    	
    	for(int i=0; i<graph.get(start).size();i++) {
    		int newIdx = graph.get(start).get(i);
    		if(visited[newIdx] == false) {
    			visited[newIdx] = true;
    			answer += 1;
    			simulate(newIdx);
    		}
    	}
    	
    }
}