글 읽기 - 런타임 에러 질문 드립니

slave_fromnowon 6년 전 1

돌리자마자 런타임 에러가 납니다. ㅠㅠ 간선 정보는 boolean형 2차원 배열의 map에 저장했구요,

dfs로 트리 생성하고, 부모들 정보도 구해놓은 뒤에

lca를 구했습니다.

어디가 문제일까요 ㅠㅠ

도와주세요.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	/**
	 * N(2 ≤ N ≤ 50,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다.
       두 노드의 쌍 M(1 ≤ M ≤ 10,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다.
	 * 
	 * ***입력
	 * 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 
	 * 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정점 쌍이 주어진다.
	 * 
	 * ***출력
	 * M개의 줄에 차례대로 입력받은 두 정점의 가장 가까운 공통 조상을 출력한다.
	 * 
	 * @param args
	 */
	
	static int N; //노드 개수
	static int M; //알고자 하는 쌍의 개수
	static int[][] p;
	static int[] d;
	static int maxD; //최고깊이
	static boolean[][] map;
	static boolean[] visit;
	
	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		N= Integer.parseInt(br.readLine().trim());
		maxD= (int) Math.floor(Math.log10(N)/Math.log10(2))+1; //노드 개수를 기준으로 나올 수 있는 최대 깊이.
		p= new int[N+1][maxD];
		d= new int[N+1];
		map= new boolean[N+1][N+1];
		visit= new boolean[N+1];
		int a, b;
		for(int i=0;i<N-1;i++){
			st= new StringTokenizer(br.readLine().trim());
			a= Integer.parseInt(st.nextToken());
			b= Integer.parseInt(st.nextToken());
			map[a][b]=true;
			map[b][a]=true;
		}
		//트리 형성
		dfs(1,0);
		//부모들 찾아놓기
		aces_find();
		
		M= Integer.parseInt(br.readLine().trim());
		int commonAce;
		StringBuffer sb= new StringBuffer();
		for(int i=0;i<M;i++){
			st= new StringTokenizer(br.readLine().trim());
			a= Integer.parseInt(st.nextToken());
			b= Integer.parseInt(st.nextToken());
			commonAce=lca(a,b);
			sb.append(commonAce+"\n");
		}
		System.out.println(sb.toString());
		
	}

	private static int lca(int a, int b) {

		//높이 맞추기
		if(d[a]>d[b]){
			int temp= a;
			a=b;
			b=temp;
		}
		
		// b의 depth를 a의 depth와 같게 올려준다.
		// b의 2^i번째 조상이 a의 depth보다 크거나 같으면 계속 조상을 타고간다.
		
		for(int i=maxD-1;i>=0;i--){
			if(d[b]-d[a] >= (1 << i)){
				b=p[b][i];
			}
		}
		
		if(a==b) return a;
		
		// a와 b가 다르다면 현재 깊이가 같으니
		// 깊이를 계속 올려 서로 다른 노드의 조상이 같아질 때까지 반복한다.
		// 즉, 서로 다른 노드(2,3)의 조상이 1로 같다면 lca = p[2][0]에 의해 2의 조상이 1임을 알 수 있고
		// 마찬가지로 p[3][0] 또한 3의 조상이 1임을 알게되며 알고리즘이 끝이난다.
		for(int i=maxD-1;i>=0;i--){
			if(p[a][i] != p[b][i]){
				a=p[a][i];
				b=p[b][i];
			}
		}
		
		return p[a][0];
	}

	private static void dfs(int a, int depth){
		d[a]=depth;
		visit[a]=true;
		for(int i=1;i<=N;i++){
			if(!visit[i] && map[a][i]){
				p[i][0]=a;
				dfs(i, depth+1);
			}
		}
		
	}
	
	private static void aces_find() {

		for(int j=1; j<maxD; j++){
			for(int i=1; i<=N;i++){
				p[i][j]=p[p[i][j-1]][j-1];
			}
		}
		
	}

}

algoshipda 6년 전 2

인접행렬이 너무 커서 그런가봐요

slave_fromnowon 6년 전 0

감사합니다 사랑해요

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

문제

문제

출처

ICPC

런타임 에러 질문 드립니

slave_fromnowon 6년 전 1

algoshipda 6년 전 2

slave_fromnowon 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말