[백준] 9372번 - 상근이의 여행

 

9372번: 상근이의 여행

 

 

그래프이론, 트리 카테고리에 속하는 문제이다. 최근 최소 신장트리 관련 문제를 접하면서 관련 기본 문제를 풀어보고 싶어서 그래프 관련 카테고리를 살펴보던 중 발견한 문제이다. 

 

문제가 요구하는 것은 상근이가 가장 적은 종류의 비행기를 타고 모든 국가를 여행할 수 있도록 하라는 것이다. 입력으로 주어지는 국가를 정점으로 보고 비행 노선을 정점간의 간선으로 생각하면 그래프 형태를 띤다. 가장 적은 적은 종류의 비행기(비행노선)를 타라는 말의 의미는 그래프를 순회하면서 모든 정점을 지나되, 그래프 내부에 사이클을 형성하지 않아야 한다는 말과 같다. 그래프 내부에 사이클이 하나 생길 때마다 타지 않아도 되는 종류의 비행기를 한 번 더 타게 되기 때문이다. 

무방향 그래프에서 모든 정점을 지나고 사이클을 형성하지 않는 것을 Spanning Tree(신장트리) 라고 부른다.

 

신장트리를 구현하는 방법은 너비우선탐색(BFS) 또는 깊이우선탐색(DFS)을 사용하면 되는데, 스텍을 사용하여 DFS를 구현하는 방법을 알게 되어 해당 방식으로 풀이하였다. 

 

 

 

 

전체 코드

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

public class Main {
    public static void main (String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int T = Integer.parseInt(br.readLine());
        
        for (int i=0; i<T; i++) {
            
            Stack<Integer> stack = new Stack<>();
            
            String[] input = br.readLine().split(" ");
            int N = Integer.parseInt(input[0]);
            int M = Integer.parseInt(input[1]);
            
            boolean[] visited = new boolean[N+1];
            List<Integer>[] link = new ArrayList[N+1];
            for (int j=1; j<=N; j++) link[j] = new ArrayList<>();
            
            
            for (int j=0; j<M; j++) {
                input = br.readLine().split(" ");
                int u = Integer.parseInt(input[0]);
                int v = Integer.parseInt(input[1]);
                link[u].add(v);
                link[v].add(u);
            }
            
            // 입력 끝
            
            // Last-in-First-out 인 스텍의 성질에 의해 출발 국가로부터 한쪽 방향으로 더 이상 방문할 국가가 없을 때까지 먼저 탐색한다.
            
            // 스텍에 시작 국가(어떠한 국가도 가능)를 넣는다.
            stack.push(1);
            int count = 0;
            
            while (!stack.isEmpty()) {
                
                // 현재 방문한 국가를 스텍에서 꺼내고 방문처리
                int now = stack.pop();
                
                visited[now] = true;
                
                for (int next : link[now]) {
                	// 현재 국가와의 비행 노선이 존재하는데 아직 방문하지 않은 국가라면 스텍에 넣는다.
                    if (!visited[next]) {
                        visited[next] = true;
                        count++;
                        stack.push(next);
                    }
                }
            }
            
            System.out.println(count);
        }
        
        br.close();
    }
}