일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
Tags
- 백준 1043번 거짓말 - java 분리 집합
- 백준 1541
- 백준 1647번 도시 분할 계획 - java
- kotlin
- 최소 힙 1927
- toUpperCase
- 프로그래머스
- 프로그래머스 자바
- replace()
- Stack
- append
- 백준 1806번 부분합 java
- 18111번 마인크래프트 - java 구현
- StringBuilder
- ac 5430번
- 백준 3190번
- 백준 1197번 최소 스패닝 트리 - java
- dp
- hash
- 백준 2467번 용액 자바 - 이분탐색
- 프로그래머스 java
- mysql hy000 에러
- 백준 2473번 세 용액 - java
- HashMap
- map
- 백준 14938번 서강그라운드
- Java
- StringTokenizer
- 코틀린기초
- HashSet
Archives
- Today
- Total
말하는 컴공감자의 텃밭
백준 11725번 트리의 부모 찾기 S1 - 트리 본문
728x90
입력들이 주루루 주어지고 1이 루트로 기준이 된다.
입력예제 처럼 주어지게 되면. 그림과 같이 입력이 들어온다.
1이 root 가 된다면 이처럼 표기할 수 있겠다.
따라서 각 자리의 부모를 나타내면
2 : 4
3 : 6
4 : 1
5 : 3
6 : 1
7 : 4 이다.
Level 별로 나타내는게 문제의 핵심이기때문에 Map에 레벨과 리스트를 넣어 tree를 구성해주었다.
static Map<Integer, List<Integer>> tree = new HashMap<>();
이후 선언된 tree에 입력을 처리할때 computeIfAbsent를 활용해서 기존 값이 있다면 추가, 없었다면 새로 리스트를 넣어주었다.
tree.computeIfAbsent(a, k -> new ArrayList<>()).add(b);
dfs 재귀를 통해서 모든 트리를 찾아 주었는데, parents 배열에 현재값의 부모를 넣어주었다.
현재 노드에 자식이 없는경우를 방지하기 위해서 getOrDefault를 통해 null 을 방지해주었다
public static void dfs(int current, int parent) {
parents[current] = parent;
for (int child : tree.getOrDefault(current, new ArrayList<>())) {
if (child != parent) {
dfs(child, current);
}
}
}
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 | import java.io.*; import java.util.*; public class Main { // Boj_11725_트리의 부모 찾기 static int N; static Map<Integer, List<Integer>> tree = new HashMap<>(); static int[] parents; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); N = Integer.parseInt(br.readLine()); parents = new int[N + 1]; for (int i = 0; i < N - 1; i++) { StringTokenizer st = new StringTokenizer(br.readLine()); int a = Integer.parseInt(st.nextToken()); int b = Integer.parseInt(st.nextToken()); tree.computeIfAbsent(a, k -> new ArrayList<>()).add(b); tree.computeIfAbsent(b, k -> new ArrayList<>()).add(a); } dfs(1, 0); StringBuilder sb = new StringBuilder(); for (int i = 2; i <= N; i++) { sb.append(parents[i]).append("\n"); } System.out.println(sb); } public static void dfs(int current, int parent) { parents[current] = parent; for (int child : tree.getOrDefault(current, new ArrayList<>())) { if (child != parent) { dfs(child, current); } } } } | cs |
728x90
'알고리즘 > Backjoon - Java' 카테고리의 다른 글
백준 1967번 트리의 지름 G4 - 트리, dfs (0) | 2024.04.17 |
---|---|
백준 1240번 노드사이의 거리 G5 - bfs (0) | 2024.04.17 |
백준 1991번 트리순회 S1 - 전위 중위 후위 순회 (0) | 2024.04.03 |
백준 23349번 졸업 사진 S1 - Hash (0) | 2024.03.28 |
백준 20408번 춘배가 선물하는 특별한 하트 G5 - Hash (0) | 2024.03.28 |
Comments