글 읽기 - 최소 스패닝 트리 알고리즘으로 안풀리나요?

filot 7년 전 0

프림을 적용했는데.. 예제는 맞는데 ..

서버에 올리니 바로 틀리네요.. ㅠㅠ

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int N;
	static int M;
	static List[] adjList;
	static int[] PATH;

	public static void main(String[] args) throws Exception {		
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

		String[] input = reader.readLine().split(" ");
		N = Integer.parseInt(input[0]);
		M = Integer.parseInt(input[1]);

		adjList = new List[N + 1];

		for (int i = 1; i <= N; i++)
			adjList[i] = new ArrayList<Edge2212>();

		for (int i = 1; i <= M; i++) {
			StringTokenizer st = new StringTokenizer(reader.readLine());

			int A = Integer.parseInt(st.nextToken());
			int B = Integer.parseInt(st.nextToken());
			int C = Integer.parseInt(st.nextToken());

			adjList[A].add(new Edge2212(A, B, C));
			adjList[B].add(new Edge2212(B, A, C));
		}

		PATH = new int[N + 1];
		prim();

		int count = 0;

		for (int i = 1; i <= N; i++)
			count += PATH[i] > 0 ? 1 : 0;

		writer.println(count);

		for (int i = 2; i <= N; i++)
			writer.println(i + " " + PATH[i]);

		writer.close();
		reader.close();
	}

	private static void prim() {
		int[] dist = new int[N + 1];
		Arrays.fill(dist, Integer.MAX_VALUE);

		Queue<Edge2212> queue = new PriorityQueue<Edge2212>();
		dist[1] = 0;
		queue.offer(new Edge2212(1, 1, 0));

		while (!queue.isEmpty()) {
			Edge2212 u = queue.poll();

			if (u.d > dist[u.v])
				continue;

			List<Edge2212> list = adjList[u.v];
			for (Edge2212 v : list) {
				if (dist[v.v] > v.d) {
					dist[v.v] = v.d;
					PATH[v.v] = v.u;

					queue.offer(new Edge2212(v.u, v.v, dist[v.v]));
				}
			}
		}
	}
}

class Edge2212 implements Comparable<Edge2212> {
	int u;
	int v;
	int d;

	public Edge2212(int u, int v, int d) {
		this.u = u;
		this.v = v;
		this.d = d;
	}

	@Override
	public int compareTo(Edge2212 o) {
		return Integer.compare(this.d, o.d);
	}
}

cokcjswo 7년 전 0

1. 최소스패닝 트리 알고리즘은 모든 노드가 연결되면서 그 간선합이 최소가 되게 하는 알고리즘입니다. 문제의 디스크립션과 상이합니다.

2. 어떤 간선들을 사용해야할까요? 반대로 어떤 간선들만 사용하면 될까요?

3. 간선들을 어떤 순서로 merge 해야할까요?

정해가 아닐 수도 있지만 제 풀이 기준으로 고민해봤던 질문들입니다.

filot 7년 전 0

결국 다익스트라로 변경하니 답이 맞네요..근데 문제를 아무리 읽어봐도 왜 다익스트라 되는건지....

모든 pc간 통신이 되어야 한다면 스패닝 트리가 되어야하지 않나 싶은데 ...

cokcjswo 7년 전 2

- 모든 점과 1 사이에 최단경로가 존재한다

-> 모든 점과 1 사이에 '경로'가 존재 하며, 이는 연결 되어 있음을 의미한다.

-> 어떤 점이든지, 1을 거쳐서 연결될 수 있다.

-> 모든 pc간 통신이 된다.

filot 7년 전 0

감사합니다. 결국 국어실력 부족 ㅠㅠ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

최소 스패닝 트리 알고리즘으로 안풀리나요?

filot 7년 전 0

cokcjswo 7년 전 0

filot 7년 전 0

cokcjswo 7년 전 2

filot 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말