[백준 Silver 3] 9372 상근이의 여행 - Java

문제링크 : https://www.acmicpc.net/problem/9372

9372번: 상근이의 여행

 

접근 과정 : 

• 문제의 접근 방법은 크게 두가지라고 생각한다.
• 먼저 지나가는 국가를 체크하면서 비행기를 타고, 모든 국가를 다 지나갔을 때, 비행기의 종류를 리턴하는 방법!
• 그런데 여기에는 약간의 함정이 있다.
• 국가를 여러번 지나가도 되고, 하나의 비행기를 여러번 타도 된다.!!
• 즉, 비행기의 종류(간선)이 최소가 되게 모든 국가를 연결하는 것인데 이는 Tree 구조이다!!!
• 따라서 다른 하나의 방법은 국가(노드)의 개수를 이용해서 비행기의 종류(간선)을 계산하는 것이다!!!

 

소스 코드 및 결과 :

package BOJ;

/* 
    상근이의 여행
    
    트리의 간선 = 노드 -1;
*/

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

public class BOJ9372 {

    public static void main(String[] args) throws NumberFormatException, IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
		int T = Integer.parseInt(br.readLine());
		
		StringBuilder sb = new StringBuilder();
		
		for (int i = 0; i<T; i++) {
            st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());

            for (int j = 0; j<M; j++) {
                br.readLine();
            }

            sb.append(N-1).append("\n");

        }
		
		System.out.println(sb.toString());
    }
}

 

package BOJ;

/* 
    상근이의 여행
    
    직접 탐색
*/


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


public class BOJ9372_copy {

    public static void main(String[] args) throws NumberFormatException, IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine());

        while (T-- > 0) {
            st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());

            List<List<Integer>> flight = new ArrayList<>();
            for(int i = 0 ;i<=N; i++){
                flight.add(new ArrayList<>());
            }

            while (M-- > 0) {
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());

                flight.get(a).add(b);
                flight.get(b).add(a);
            }

            boolean[] visit = new boolean[N + 1];

            sb.append(trip(flight, visit, 1)).append("\n");


        }

        System.out.println(sb.toString().trim());

    }

    static int trip(List<List<Integer>> flight, boolean[] visit, int now) {

        visit[now] = true;

        int fly = 0;

        for (int next : flight.get(now)) {
            if (visit[next]) {
                continue;
            }

            fly += (trip(flight, visit, next)+1);
        }

        return fly;
    }
}

 

P.S 

문제를 보고, 사용될 혹은 구성될 자료구조를 잘 파악하는게 주요 관점이지 않나 싶다.

나도.. 직접 탐색하는 알고리즘을 작성하고 나서 Tree 구조를 인지하게 되었다..

어쩐지 작성할 때, 이상하더라니..