트리의 부모 찾기
시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 256 MB 27396 11727 8664 42.697% 문제
루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.
출력
첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.
예제 입력 1
7 1 6 6 3 3 5 4 1 2 4 4 7
예제 출력 1
4 6 1 3 1 4
예제 입력 2
12 1 2 1 3 2 4 3 5 3 6 4 7 4 8 5 9 5 10 6 11 6 12
예제 출력 2
1 1 2 3 3 4 4 5 5 6 6
출처
문제를 만든 사람: baekjoon
잘못된 조건을 찾은 사람: jh05013
알고리즘 분류
풀이 방법
bfs 방법을 이용해서 풀었다. 방향이 없이 연결되어 있기 때문에 Arraylist배열인 lists를 이용해서 양쪽을 전부 나타내 주었다.
1을 루트로 하기 때문에 queue에 먼저 넣어서 bfs로 찾아갔다.
내 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
boolean[] check = new boolean[n];
List<Integer>[] lists = new ArrayList[n];
int[] parent = new int[n];
for (int i = 0; i < lists.length; i++) {
lists[i] = new ArrayList<>();
}
for (int i = 1; i < n; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken()) - 1;
int b = Integer.parseInt(st.nextToken()) - 1;
lists[a].add(b);
lists[b].add(a);
}
Queue<Integer> q = new LinkedList<>();
q.add(0);
check[0] = true;
while (!q.isEmpty()) {
int num = q.poll();
check[num] = true;
for (Integer integer : lists[num]) {
if (!check[integer]) {
q.add(integer);
parent[integer] = num + 1;
}
}
}
for (int i = 1; i < parent.length; i++) {
System.out.println(parent[i]);
}
}
}
'코딩테스트 > [백준] 코딩테스트 연습' 카테고리의 다른 글
최단경로 - 1753번 (0) | 2021.10.01 |
---|---|
동전 2 - 2294번 (0) | 2021.09.29 |
1로 만들기 - 1463번 (0) | 2021.09.29 |
나는야 포켓몬 마스터 이다솜 - 1620번 (0) | 2021.09.23 |
요세푸스 문제 - 1158번 (0) | 2021.09.23 |