글 읽기 - java 어느 부분이 잘못되었는지 잘 모르겠습니다ㅠㅠ

imfksh 3년 전 1

초보라서 코드가 간결하지 못한점 이해 부탁드립니다.

MST를 먼저 구현한 다음

두 점의 LCA 와 그 사이 간선들 중 가중치가 가장 높은 것을 리턴 받아서 계산 했는데..

제출하니까 그냥 채점 자체가 안되네요.

0% 계산도 안됨..

어느 부분에서 잘못되었는지 고수님들의 가이드 살짝만 부탁드리겠습니다.

미리 감사합니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Main {

	static int N;
	static int Q;
	static int K = 20;
	
	static ArrayList<Route> rlist;
	static ArrayList<Route> rlist2;
	
	static int [] root;
	static int [] rank;
	
	static int [][] parent;
	static int [][] high;
	static int [] depth;
	
	
	static ArrayList<Integer> [] nlist;
	static ArrayList<Integer> [] clist;

	static boolean [] visited;
	
	static int mst;
	static int templca;
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		Q = Integer.parseInt(st.nextToken()); 
		
		rlist = new ArrayList<Route>();
		rlist2 = new ArrayList<Route>();
		
		for (int i = 1; i<=Q; i++) {
			st = new StringTokenizer(br.readLine());
			int s =Integer.parseInt(st.nextToken());
			int e =Integer.parseInt(st.nextToken());
			int c =Integer.parseInt(st.nextToken());
			rlist.add(new Route(s,e,c, false));
			rlist2.add(new Route(s,e,c, false));
		}
		
		Collections.sort(rlist, new Comparator<Route>() {

			@Override
			public int compare(Route a, Route b) {
				// TODO Auto-generated method stub
				if (a.c < b.c) {
					return -1;
				} else if (a.c> b.c) {
					return 1;
				} else {
					return 0;
				}
			}
		});
		
		root = new int [N+1];
		rank   = new int [N+1];
		
		for (int i = 1; i<=N; i++) {
			root[i] = i;
		}
		
		mst = 0;
		int count = 0;

		for (int i = 0; i<rlist.size(); i++) {
			
			int x = rlist.get(i).s;
			int y = rlist.get(i).e;
			int z = rlist.get(i).c;
			
			if (!isSameParent(x,y)) {
				union(x,y);
				mst+=z;
				count++;
				rlist.get(i).flag = true;
			}
			if (count >= N-1) break; 
			
		}

		// lca 시작

		depth = new int [N+1];
		visited = new boolean [N+1];
		
		parent = new int [N+1][K];
		high   = new int [N+1][K];
		
		
		nlist = new ArrayList [N+1];
		clist = new ArrayList [N+1];
				
		for (int i = 1; i<=N; i++) {
			nlist[i] = new ArrayList<Integer>();
			clist[i] = new ArrayList<Integer>();			
		}
		
		for (int i = 0; i<Q; i++) {
			int s = rlist.get(i).s;
			int e = rlist.get(i).e;
			int c = rlist.get(i).c;
			nlist[s].add(e);
			nlist[e].add(s);
			clist[s].add(c);
			clist[e].add(c);
		}
		
						
		dfs(1, 0, 0);
		
		fillParent();

		for (int i = 0; i<rlist2.size(); i++) {
			
			int x = rlist2.get(i).s;
			int y = rlist2.get(i).e;
			int z = rlist2.get(i).c;
			
			int lca = getLCA(x,y);
						
			int answer = mst-lca+z;
			
			System.out.println(answer);
			
		}
		
		
		
		
	}

	private static int getLCA(int a, int b) {
		// TODO Auto-generated method stub
		int answera = 0;
		int answerb = 0;
		
		// 높이 비교						
		if (depth[a] < depth[b]) {
			int temp = b;
			b = a; 
			a = temp;
		}
		
		// 높이 맞추기
		for (int i = K-1; i>=0; i--){
			int diff = depth[a] - depth[b];
			if ((diff & (1<<i)) != 0) {
				answera = Math.max(answera, high[a][i]);
				a = parent[a][i];
			}
		}
		
		if (a==b) return answera;
		
		for (int i = K-1; i>=0; i--) {
			if (parent[a][i] != parent[b][i]) {
				answera = Math.max(answera, high[a][i]);
				answerb = Math.max(answerb, high[b][i]);
				a = parent[a][i];
				b = parent[b][i];
			}
		}
		answera = Math.max(answera, high[a][0]);
		answerb = Math.max(answerb, high[b][0]);
		
		return Math.max(answera, answerb);

	}


	private static void fillParent() {
		// TODO Auto-generated method stub
		for (int i = 1; i<K; i++) {
			for (int j = 1; j<=N; j++) {
				parent[j][i] = parent[parent[j][i-1]][i-1];
				high  [j][i] = Math.max(high[j][i-1], high[parent[j][i-1]][i-1]);
			}
		}
		
	}

	private static void dfs(int node, int dep, int hig) {
		// TODO Auto-generated method stub
		depth[node] = dep;
		visited[node] = true;
		
		for (int i = 0; i<nlist[node].size(); i++) {
			
			int x = nlist[node].get(i);
			
			if (!visited[x]) {				
				parent[x][0] = node;
				//high[x] = Math.max(hig, clist[node].get(i));			
				high[x][0] = clist[node].get(i);		
				dfs(x, dep+1,high[x][0]);
			}
			
		}
		
		
	}


	private static void union(int x, int y) {
		// TODO Auto-generated method stub
		if (rank[x] < rank[y]) {
			root[x] = y;
		} else if (rank[x] > rank[y]) {
			root[y] = x;
		} else {
			root[y] = x;
			rank[x]++;
		}
		
		
	}


	private static boolean isSameParent(int x, int y) {
		// TODO Auto-generated method stub
		int a = find(x);
		int b = find(y);
		if (a==b) return true;
		else	return false;
	}


	private static int find(int x) {
		// TODO Auto-generated method stub
		if (x == root[x]) return x;
		else return root[x] = find(root[x]);
	}


	static class Route{
		int s;
		int e;
		int c;
		boolean flag;
		public Route(int s, int e, int c, boolean flag) {
			super();
			this.s = s;
			this.e = e;
			this.c = c;
			this.flag = flag;
		}
		
	}
	
}

rhtkdwls 3년 전 0

안녕하세요!

저는 알고리즘을 잘하는 사람도 아니고, 코드를 완벽하게 보진 못했지만 도움이 됐으면 좋겠네요.

먼저 문제를 어떻게 풀어야 하는 지는 개략적으로 알고 계신 것 같습니다. 다만, MST를 만들면서 만들어진 MST를 토대로 LCA를 구축해야하는데, MST는 MST대로, LCA는 LCA대로 만들고 계신 것 같습니다.(이를 위해 flag 변수를 만드신 것 같지만, flag변수가 쓰이지는 않네요)

Prim 알고리즘으로 MST에 필요한 간선을 하나씩 추가면서, 동시에 LCA도 만드는 방법은 어떨까요?

아니면 Kruskal로 MST를 만들었을 때 사용된 간선들만 모아서, 이 간선들을 가지고 LCA를 만드는 방법은 어떨까요?

그리고, 코드에서 선언은 됐지만 쓰이지 않는 부분들이 있습니다. 개인적으로, 코드가 길어지면 해당 코드가 틀렸을 때 어느 부분에 문제가 있는지 확인하기가 어렵더라고요.

그래도 좋은 결과 있었으면 좋겠습니다.

화이팅!

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

문제

문제

출처

ICPC

java 어느 부분이 잘못되었는지 잘 모르겠습니다ㅠㅠ

imfksh 3년 전 1

rhtkdwls 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말