[SWEA] 1248. 공통조상

문제

1248. [S/W 문제해결 응용] 3일차 - 공통조상
이진트리가 주어진다.
두 정점의 가장 가까운 공통조상과, 그 공통조상부터 시작하는 서브트리의 크기를 출력하라.

풀이

DFS+재귀로 풀었다.
두 정점을 N1,N2라고 하자.
N1의 서브트리를 조사해서 N2가 있는지 찾는다.
- DFS()
- N2가 있으면 isFind = true
- 발견했어도 일단 끝까지 탐색해서 서브트리의 크기를 늘린다. (count)
없으면 부모노드로 가서 방금 확인하지 않은 자식노드의 서브트리를 조사해서 N2를 찾는다.
없으면 부모노드로 가서 ... (재귀)

자바코드

package problemsolving;

import java.util.Scanner;
import java.io.FileInputStream;


class Solution
{
	static final int MAX = 10001; // 10000 + 1
	static int [] parent = new int[MAX]; // 0 : 부모없음 
	static int [][] child = new int[MAX][2]; // 0 : 자식없음 
	static int count;
	static boolean isFind;
	public static void main(String args[]) throws Exception
	{
		// System.setIn(new FileInputStream("res/input.txt"));


		Scanner sc = new Scanner(System.in);
		int T;
		T=sc.nextInt();
		int V, E, N1, N2;
		for(int test_case = 1; test_case <= T; test_case++)
		{
			V = sc.nextInt();
			E = sc.nextInt();
			N1 = sc.nextInt();
			N2 = sc.nextInt();
			
			init(V);
			
			int p, c;
			for (int i=0; i<E; i++) {
				p = sc.nextInt();
				c = sc.nextInt();
				parent[c] = p;
				if (child[p][0]==0) child[p][0] = c;
				else child[p][1] = c;
			}
			
			System.out.printf("#%d %d %d\n", test_case, search(N1, 0, N2), count);
		}
	}
	
	public static void init(int V) {
		count = 0;
		isFind = false;
		
		for (int i=1; i<=V; i++) {
			parent[i] = 0;
			child[i][0] = 0;
			child[i][1] = 0;
		}
	}
	
	public static int search(int start, int skipChild, int target) {
		// 자식 다돌고 (서브트리 카운트++)
		DFS(start, skipChild, target);
		
		// 못찾았으면 부모호출 
		if (!isFind) return search(parent[start], start, target);
		else return start;
	}
	
	public static void DFS(int start, int skipChild, int target) {
		if (start == skipChild) return;
		count++;
		for (int i=0; i<2; i++) {
			if (child[start][i] == 0) continue;
			if (child[start][i] == target) isFind = true;
			DFS(child[start][i], skipChild, target);
		}
	}
}

틀린이유

Memory error occured, (e.g. segmentation error, memory limit Exceed, stack overflow,... etc)

아무리 찾아도 메모리 사용에 잘못된 부분이 없었다ㅜ 코드에 이상도 없었다 ㅜ
한 줄씩 다 지워보다 발견한

System.setIn(new FileInputStream("res/input.txt"));

...ㅜㅠ
SWEA에선 이거 제발 지우고 제출하자.