글 읽기 - 9%에서 통과가 안됩니다. (java)

godhs96 3년 전 0

안녕하세요.

최소스패닝이론을 먼저 공부하지 않은 상태에서 코드를 짜봤습니다.

알고리즘은 다음과 같습니다.

1. 정점 방문 배열을 생성

2. 우선순위 큐를 이용하여 최소 간선인 것 부터 꺼내기

3. 만약 두 정점이 모두 방문된 상태면 pass (이미 연결된 간선이기 때문)

4. 두 정점 중에 하나라도 방문되지 않은 상태면 해당 간선의 가중치를 ans에 더함

5. q가 끝날 때까지 반복

시간초과도 아니고 그냥 틀려버리고 이전 질문들의 반례들을 넣어봐도 잘 동작합니다.

감사합니다.

package bfs_dfs;

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

public class B_1197 {
	
	public static class Node implements Comparable<Node>{
		int start;
		int end;
		int v;
		
		Node(int start, int end, int v) {
			this.start = start;
			this.end = end;
			this.v = v;
		}
		
		@Override
		public int compareTo(Node n) {
			return this.v - n.v;
		}
	}

	public static void main(String[] args) throws IOException {
		//1. 정점 visit를 생성
		//2. PriorityQueue를 이용하여 최소 가중치부터 꺼낸 후 그래프 연결
		//3. 두 정점이 visit되지 않은 경우, 간선 연결
		//4. 두 간선이 방문된 점이면 넘기기
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		int V = Integer.parseInt(st.nextToken());
		int E = Integer.parseInt(st.nextToken());
		
		boolean[] visitV = new boolean[V+1]; // 정점 방문 노드				
		
		PriorityQueue<Node> q = new PriorityQueue<>();
		
		for(int i=0; i<E; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			
			q.add(new Node(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
		}
		
		long ans = 0;
		
		while(!q.isEmpty()) {
			Node cur = q.poll();
			
			if(visitV[cur.start] && visitV[cur.end]) { // 두 정점이 모두 방문된 상태 -> 이미 해당 간선이 연결된 상태
				continue;
			} 
			
			visitV[cur.start] = true;
			visitV[cur.end] = true;
			ans += cur.v;
		}		
		
		System.out.println(ans);
	}
}

adxx 3년 전 2

저는 알고리즘 청정수지만 이렇게 생각해보면 어떨까요?

그러니까 모든 간선들이 두가지로 나뉘어진 상태를 가정해보는거죠

왼쪽에 있는 간선들끼리는 모두 서로 연결된 상태이고(acyclic하게) 오른쪽도 마찬가지 상태일때, 이 두가지 component를 연결하는 가장 작은 간선이 MST에 포함되는건 당연해 보여요

그런데 이 간선은 질문자님이 말씀해주신 알고리즘에서는 이미 방문 된 간선으로 "오해"를 하고 있는 것 같은데 반례가 되었을까요?

puyol 3년 전 1

adxx님 말씀이 맞습니다.

쉽게 말해 1부터 4까지 4개의 정점이 있을 때

1과 2를 연결하고 (VisitV[1] = true, VisitV[2] = true)

3과 4를 연결하면 (VisitV[3] = true, VisitV[4] = true)

아직 1-2 와 3-4의 연결은 이루어지지 않았지만,

프로세스가 더 나가지 못하고 종료됩니다.

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

문제

문제

출처

ICPC

9%에서 통과가 안됩니다. (java)

godhs96 3년 전 0

adxx 3년 전 2

puyol 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말