오답노트 #15681 : 트리와 쿼리

풀이방법 및 문제점

2022.02.12

55%에서 시간초과가 난다. 예제의 답은 옳게 출력된다.

일단은 출력 방식을 바꾸어봐야겠다. 18870번 문제를 풀 때처럼 System.out.println을 Q번 수행한 것이 문제일 수 있다.

혹은 재귀함수를 많이 써서 시간이 많이 걸린 것일까?

트리를 생성하는 makeTree 함수도 재귀함수이고, 서브트리의 노드의 개수를 구하는 count 함수도 재귀함수이다.

하지만 재귀를 쓰지 않는 방식이 떠오르지 않는다. 자고 일어나서 생각해봐야겠다.

혹은 트리의 구현 방식이 문제일 수도 있다. 다른 방식으로 구현해봐야겠다. 자바에서 트리 형식의 라이브러리를 제공하는지도 알아봐야겠다.

 

사용한 풀이 방법은 다음과 같다.

 

먼저, n-1개의 간선 정보를 인접 리스트(ArrayList<Integer>[] connect)에 저장하였다.

connect에 담긴 정보를 이용하여 재귀적으로 트리를 생성하는 makeTree 함수를 짰다. 그 내용은 다음과 같다.

 

makeTree 함수의 인자는 이번에 처리할 노드의 번호(cur)와 해당 노드의 부모노드의 번호(p)이다.

루트의 경우에는 p 값을 0으로 설정하였다.

cur번째 노드가 루트일 경우, cur번째 노드와 연결된 모든 노드들은 cur번째 노드의 자식이다.

그러므로 connect[cur]에 기록된 모든 노드를 자식으로 추가한다.

cur번째 노드가 루트가 아닐 경우, cur번째 노드와 연결된 요소들 중 하나가 cur번째 노드의 부모이고 나머지는 모두 자식이다.

그러므로 connect[cur]에 기록된 모든 노드에 대하여 해당 노드가 cur번째 노드의 부모가 아니라면 자식으로 추가한다.

이 과정을 모든 노드에 대하여 루트에서부터 차근차근 재귀적으로 수행한다.

 

서브트리의 노드 개수를 구하는 count 함수는 DFS 방식으로 서브트리를 모두 방문하며 방문시마다 cnt 값을 1씩 늘려주는 함수이다.

 

2022.02.13

StringBuilder를 사용하여 출력에 걸리는 시간을 줄여보았다.

채점 속도가 확실히 빨라졌지만 여전히 55%에서 시간초과가 난다.

 

2022.02.23

풀었다!

피보나치 수열처럼 DP를 이용해 풀면 된다.

동적 프로그래밍으로 서브노드개수를 미리 구해 저장해두는 게 정답이었다.

 

벌써 이런 문제가 몇 개째인지 모르겠다. 계속 똑같은 실수를 한다.

재귀로 풀어보려고 머리 싸매지 말고 동적 프로그래밍을 기억하자. 개고생했으니 잊지 말자!!!

정답 게시물 바로가기

 

코드

Java(2022.02.12)

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

public class Main {
	
	static Node[] tree;
	static int cnt;
	static ArrayList<Integer>[] connect;
	
	//간선정보를 바탕으로 트리를 생성하는 함수
	static void makeTree(int cur, int p) {
		//cur은 현재 처리중인 노드의 번호, p는 해당 노드의 부모노드의 번호
		if(p == 0) {
			for(int n : connect[cur]) {
				tree[cur].childs.add(tree[n]);
				tree[n].parent = tree[cur];
				makeTree(n, cur);				
			}
		}
		else {
			tree[cur].parent = tree[p];
			
			for(int n : connect[cur]) {
				if(tree[cur].parent.name != n) {
					tree[cur].childs.add(tree[n]);
					tree[n].parent = tree[cur];
					makeTree(n, cur);
				}
			}
		}
	}
	
	//자신을 포함하여, 서브트리의 노드 개수를 세는 함수
	static void count (Node n) {
		cnt++;
		
		for(Node m: n.childs) {
			count(m);
		}
		
	}

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		//n, r, q 읽어오기
		String[] s = br.readLine().split(" ");
		int[] nrq = new int[3];
		for(int i = 0; i<3; i++) {
			nrq[i] = Integer.parseInt(s[i]);
		}
		
		//n개의 노드를 가진 트리 선언
		tree = new Node[nrq[0]+1];
		for(int i = 1 ;i< nrq[0]+1; i++) {
			tree[i] = new Node(i);
		}
		
		//n-1개의 간선 정보를 읽어와 트리 구성하기
		connect = new ArrayList[nrq[0]+1];
		for(int i = 1; i<nrq[0]+1; i++) {
			connect[i] = new ArrayList<Integer>();
		}
		for(int i = 0; i<nrq[0]-1; i++) {
			//읽어오기
			String[] input = br.readLine().split(" ");
			int[] con = new int[2];
			for(int j = 0; j<2; j++) {
				con[j] = Integer.parseInt(input[j]);
			}
			connect[con[0]].add(con[1]);
			connect[con[1]].add(con[0]);
		}
		
		makeTree(nrq[1],0);
		
		//q개의 쿼리에 답하기
		for(int i = 0; i<nrq[2]; i++) {
			int q = Integer.parseInt(br.readLine());
			cnt = 0;
			count(tree[q]);
			System.out.println(cnt);
		}
	}

}

//노드 클래스
class Node{
	public int name;	//노드 이름(번호)
	public Node parent;	//부모
	public ArrayList<Node> childs;	//자식들
	
	//생성자
	public Node(int name) {
		this.name = name;
		childs = new ArrayList<Node>();
	}
}

Java(2022.02.13)

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

public class Main {
	
	static Node[] tree;
	static int cnt;
	static ArrayList<Integer>[] connect;
	
	//간선정보를 바탕으로 트리를 생성하는 함수
	static void makeTree(int cur, int p) {
		//cur은 현재 처리중인 노드의 번호, p는 해당 노드의 부모노드의 번호
		if(p == 0) {
			for(int n : connect[cur]) {
				tree[cur].childs.add(tree[n]);
				tree[n].parent = tree[cur];
				makeTree(n, cur);				
			}
		}
		else {
			tree[cur].parent = tree[p];
			
			for(int n : connect[cur]) {
				if(tree[cur].parent.name != n) {
					tree[cur].childs.add(tree[n]);
					tree[n].parent = tree[cur];
					makeTree(n, cur);
				}
			}
		}
	}
	
	//자신을 포함하여, 서브트리의 노드 개수를 세는 함수
	static void count (Node n) {
		cnt++;
		
		for(Node m: n.childs) {
			count(m);
		}
		
	}

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		//n, r, q 읽어오기
		String[] s = br.readLine().split(" ");
		int[] nrq = new int[3];
		for(int i = 0; i<3; i++) {
			nrq[i] = Integer.parseInt(s[i]);
		}
		
		//n개의 노드를 가진 트리 선언
		tree = new Node[nrq[0]+1];
		for(int i = 1 ;i< nrq[0]+1; i++) {
			tree[i] = new Node(i);
		}
		
		//n-1개의 간선 정보를 읽어와 트리 구성하기
		connect = new ArrayList[nrq[0]+1];
		for(int i = 1; i<nrq[0]+1; i++) {
			connect[i] = new ArrayList<Integer>();
		}
		for(int i = 0; i<nrq[0]-1; i++) {
			//읽어오기
			String[] input = br.readLine().split(" ");
			int[] con = new int[2];
			for(int j = 0; j<2; j++) {
				con[j] = Integer.parseInt(input[j]);
			}
			connect[con[0]].add(con[1]);
			connect[con[1]].add(con[0]);
		}
		
		makeTree(nrq[1],0);
		
		//q개의 쿼리에 답하기
		StringBuilder sb = new StringBuilder();
		for(int i = 0; i<nrq[2]; i++) {
			int q = Integer.parseInt(br.readLine());
			cnt = 0;
			count(tree[q]);
			sb.append(cnt + System.getProperty("line.separator"));
		}
		System.out.print(sb);
	}

}

//노드 클래스
class Node{
	public int name;	//노드 이름(번호)
	public Node parent;	//부모
	public ArrayList<Node> childs;	//자식들
	
	//생성자
	public Node(int name) {
		this.name = name;
		childs = new ArrayList<Node>();
	}
}