728x90
문제
루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.
출력
첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.
방법 자체는 dfs를 이용하면 돼서 어렵지 않은데, 메모리와 시간 초과 때문에 오래 걸렸다.
1을 루트로 하기 때문에 1을 시작으로 해서 dfs를 진행하고, 부모 노드를 찾아야 해서 HashMap에 각 child의 부모 노드를 value로 하여 값을 추가하였다.
처음에는 dfs를 각 노드를 찾을 때마다 반복해서 시간이 오래 걸렸는데, dfs는 1을 정점으로 하여 한 번만 진행하면 모든 tree에 대해 간선이 정리되기 때문에 반복할 필요가 없었다.
또 처음에는 2차원 배열로 간선들을 저장하였는데, 이러니 메모리 초과가 났다. 그래서 LinkedList에 각 값을 추가하는 식으로 변경하였다.
package Silver.s2;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.StringTokenizer;
public class BOJ_11725_TreeParent {
static LinkedList<Integer>[] arr;
static LinkedList<Boolean>[] visited;
static int N;
static HashMap<Integer, Integer> tree = new HashMap<>(); // key는 child, value는 parent
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
arr = new LinkedList[N + 1];
visited = new LinkedList[N + 1];
for (int i = 0; i < N + 1; i++) {
arr[i] = new LinkedList<Integer>(); // i의 자식노드만 남기기
visited[i] = new LinkedList<Boolean>();
}
for (int i = 0; i < N - 1; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int v1 = Integer.parseInt(st.nextToken());
int v2 = Integer.parseInt(st.nextToken());
arr[v1].add(v2);
arr[v2].add(v1);
visited[v1].add(false);
visited[v2].add(false);
}
dfs(1);
for (int i = 2; i <= N; i++) {
sb.append(tree.get(i) + "\n");
}
System.out.print(sb.toString());
}
static void dfs(int parent) {
for (int i = 0; i < arr[parent].size(); i++) {
if (!visited[parent].get(i)) {
int child = arr[parent].get(i);
if (!tree.containsKey(child))
tree.put(child, parent); // 자식 노드 추가
visited[parent].set(i, true);
int parentIdx = arr[child].indexOf(parent);
visited[child].set(parentIdx, true);
dfs(child);
visited[parent].set(i, false);
visited[child].set(parentIdx, false);
}
}
}
}
728x90
'문제 풀이 > BOJ' 카테고리의 다른 글
[백준] 1991 - 트리 순회 (0) | 2022.08.24 |
---|---|
[백준] 1182 - 부분수열의 합 (자바/Java) 재귀 부분집합 (0) | 2022.08.24 |
[백준] 2116 - 주사위 쌓기 (자바/Java) (0) | 2022.08.23 |
[백준] 17276 배열 돌리기 (자바/Java) (0) | 2022.08.22 |
[백준] 10866 - 덱 Deque (자바/Java) (0) | 2022.08.18 |