[백준/자바] 9372번: 상근이의 여행

문제

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

풀이

• N개국을 여행
• 최대한 적은 종류의 비행기를 타고 이동하려고 함

문제까지만 읽었을 땐 단순한 그래프 탐색 문제라고 생각할 수 있습니다.
하지만, 문제에서 상근이는 주어진 "모든 나라"를 탐색해야 한다고 했습니다.
입력을 보시면 (출발 나라 -> 도착 나라) 꼴로 주어집니다.
간선은 주어졌지만, 가중치는 주어지지 않은(가중치가 동일한) 그래프임을 알 수 있죠

저는 이 문제를 DFS와 최소 신장 트리의 성질을 이용해 풀어보겠습니다.

입력(DFS)

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());
		while (t-- > 0) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			n = Integer.parseInt(st.nextToken());
			m = Integer.parseInt(st.nextToken());
			
			graph = new ArrayList<>();
			for (int i = 0; i <= n; i++) graph.add(new ArrayList<>());
			
			for (int i = 0; i < m; i++) {
				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);
			}
            
            visited = new boolean[n+1];

• t: 테스트케이스
• n: 나라 수
• m: 비행기 노선의 수
• graph: 비행기의 노선 정보를 저장할 배열
• visited: 각 나라의 방문 여부를 알 수 있는 배열

DFS

	private static int dfs(int cur, int cnt) {
		visited[cur] = true;
		for (int nxt : graph.get(cur)) {
			if (!visited[nxt]) {
				cnt = dfs(nxt, cnt + 1);
			}
		}
		return cnt;
	}

• cur: 현재 나라
• cnt: 지나간 노선의 수
• 탐색 시작 시, 현재 나라를 방문 처리합니다.
• 현재 나라와 연결된 나라들을 탐색하여, 방문하지 않은 나라라면 재귀해 줍니다.(cnt 증가 필수)
• 만약 모든 나라를 다 탐색했다면, cnt를 리턴하여 값을 구해줍니다.

출력

			int answer = dfs(1, 0);
			System.out.println(answer);

• 리턴 받은 cnt를 출력하면 끝

---

입력(MST)

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());
		while (t-- > 0) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int n = Integer.parseInt(st.nextToken());
			int m = Integer.parseInt(st.nextToken());
			
			for (int i = 0; i < m; i++) {
				br.readLine();
			}

• 모두 동일합니다.

그러나 왜 각 나라의 노선을 입력받지 않았는지 궁금하실텐데요.
저희는 어차피 1부터 n까지의 모든 나라를 방문해야 합니다.
이말은 즉슨 1부터 n까지의 노선이 모두 주어질 것을 알 수 있습니다.
최소 신장 트리의 성질은 간선의 수가 (노드의 수 - 1)입니다.
어차피 모든 나라는 연결이 될 것이고, 그 중 가중치의 합이 최소인 경우에 간선 n-1개를 사용하면 최소 간선 수를 사용하게 되는 것이죠.

이 성질을 이용하여

출력(MST)

			System.out.println(n - 1);

• n-1을 출력하면 끝입니다.

코드(DFS)

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

public class Main_9372 {
	
	static int n, m;
	static boolean[] visited;
	static List<ArrayList<Integer>> graph;
	
	private static int dfs(int cur, int cnt) {
		visited[cur] = true;
		for (int nxt : graph.get(cur)) {
			if (!visited[nxt]) {
				cnt = dfs(nxt, cnt + 1);
			}
		}
		return cnt;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());
		while (t-- > 0) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			n = Integer.parseInt(st.nextToken());
			m = Integer.parseInt(st.nextToken());
			
			graph = new ArrayList<>();
			for (int i = 0; i <= n; i++) graph.add(new ArrayList<>());
			
			for (int i = 0; i < m; i++) {
				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);
			}
			
			visited = new boolean[n+1];
			int answer = dfs(1, 0);
			System.out.println(answer);
		}
	}

}

코드(MST)

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

public class Main_9372 {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());
		while (t-- > 0) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int n = Integer.parseInt(st.nextToken());
			int m = Integer.parseInt(st.nextToken());
			
			for (int i = 0; i < m; i++) {
				br.readLine();
			}
			
			System.out.println(n - 1);
		}
	}

}