[백준 JAVA] 13418번: 학교 탐방하기

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

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	public static int N, M, best = 0, worst = 0, ans = 0;
	public static int[] visited;
	public static List<int[]>[] list;
	public static int[][] graph;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		// 1. 입력받기
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		visited = new int[N + 1];
		list = new ArrayList[N + 1];
		for (int i = 0; i <= N; i++) {
			list[i] = new ArrayList<>();
		}

		for (int i = 0; i < M + 1; i++) {
			st = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			int value = Integer.parseInt(st.nextToken());

			list[from].add(new int[] { to, value });
			list[to].add(new int[] { from, value });
		}

		// 2. 최소거리
		PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> Integer.compare(o1[1], o2[1]));

		pq.add(new int[] { 0, 1 });

		while (!pq.isEmpty()) {
			int[] cur = pq.poll();
			int to = cur[0];
			int value = cur[1];

			// 간선 비용 비교
			if (visited[to] == 1)
				continue;

			visited[to] = 1;
			if (value == 0) {
				best += 1;
			}

			for (int i = 0; i < list[to].size(); i++) {
				int[] hae = list[to].get(i);

				if (visited[hae[0]] == 0) {
					pq.add(new int[] { hae[0], hae[1] });
				}
			}
		}

		// 3. 최장거리
		PriorityQueue<int[]> pq2 = new PriorityQueue<>((o1, o2) -> Integer.compare(o2[1], o1[1]));

		pq2.add(new int[] { 0, 1 });

		while (!pq2.isEmpty()) {
			int[] cur = pq2.poll();
			int to = cur[0];
			int value = cur[1];

			// 간선 비용 비교
			if (visited[to] == 0)
				continue;

			visited[to] = 0;
			if (value == 0) {
				worst += 1;
			}

			for (int i = 0; i < list[to].size(); i++) {
				int[] hae = list[to].get(i);

				if (visited[hae[0]] == 1) {
					pq2.add(new int[] { hae[0], hae[1] });
				}
			}
		}
		ans = (int) (Math.pow(best, 2) - (Math.pow(worst, 2)));

		// 4. 출력하기
		System.out.println(ans);

	}
}

 

 

풀이 사항

풀이 일자: 2024.09.24
풀이 시간: 60분
채점 결과: 정답
예상 문제 유형: MST

풀이 방법

1. 최소신장트리, 최대신장트리를 사용해서 풀이하였다.
2. 문제를 잘못읽고 오르막길이면 반대에서는 내리막길이라고 생각해서 이해하는데 오래걸렸다.
3. 오르막길이 1이고 내리막길이 0이라고 생각해서 잘못풀어서 오류가 생겼다.
4. 문제를 잘 읽고 풀자