11725번: 트리의 부모 찾기
루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.
www.acmicpc.net
> 의식의 흐름
> 풀이 과정
1. 연결된 노드 담기
2. 1번 노트부터 시작 (트리의 루트를 1이라고 정했기 때문)
3. 현재 노드(nowIdx)와 연결된 노드들의 부모 설정하기 (parents[])
4. 2번 노드부터 부모 출력
> 코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main {
public static int N; // 노드의 개수
public static ArrayList<ArrayList<Integer>> links = new ArrayList<>(); // 연결된 노드 담기
public static boolean[] visited;
public static int[] parents;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
N = Integer.parseInt(br.readLine());
for(int i=0;i<=N;i++){
links.add(new ArrayList<Integer>());
}
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());
links.get(a).add(b);
links.get(b).add(a);
}
// 부모 찾기
visited = new boolean[N+1];
parents = new int[N+1];
findParents(1, 1);
for(int i=2;i<=N;i++){
bw.write(Integer.toString(parents[i])+"\n");
}
bw.flush();
br.close();
bw.close();
}
public static void findParents(int nowIdx, int parentIdx){
visited[nowIdx] = true;
parents[nowIdx] = parentIdx;
for(int i:links.get(nowIdx)){
if(!visited[i])
findParents(i, nowIdx);
}
}
}
'알고리즘 > 백준' 카테고리의 다른 글
[JAVA] 백준 q5639 - 이진 검색 트리 (0) | 2023.10.04 |
---|---|
[JAVA] 백준 q1991 - 트리 순회 (0) | 2023.09.21 |
[JAVA] 백준 q14675 - 단절점과 단절선 (0) | 2023.09.19 |
[JAVA] 백준 q7662 - 이중 우선순위 큐 (0) | 2023.09.15 |
[JAVA] 백준 q4358 - 생태학 (0) | 2023.09.14 |