백준 15681 트리와 쿼리 java
https://www.acmicpc.net/problem/15681그래프가 주어지고. 특정 노드를 루트로 삼아서 트리처럼 관리해야한다.시간제한이 1초인데 10만개의 정점과 쿼리가 주어질 수 있기에 최악의 상황(트리가 1자로 쭉 이어짐)에서 매번 트리를 탐색하며 갯수를 세면 시간초과가 될 수 밖에 없다. 처음구현했던 단순한 방법1과 좀더 가다듬은 방법2 를 기술한다. 방법1.인접리스트를 저장한 그래프를 만들고, 입력된 루트를 기반으로 그래프를 트리로 재구성한 뒤루트에서부터 트리를 재귀호출로 탐색하며 서브트리의 크기를 갱신한다.import java.lang.reflect.Array;import java.util.*;import java.io.*;import java.lang.*;public class Mai..
baekjoon
2024. 12. 1. 23:27
