[백준] 11725 트리의 부모 찾기(Java)
문제링크
문제분석
- 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.
- 노드의 연결 관계를 표현하기 위해 연결 리스트 사용 : N<=100,000 이므로 이차원 배열을 선언하면 메모리가 초과된다.
- 노드를 입력 받을 때는, 부모 자식 간 구분이 없으므로 양방향으로 저장한다.
입력
- 첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.
출력
- 첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.
풀이
- 큐를 이용해 루트노드(1번 노드)부터 탐색을 해나간다. 현재 노드와 연결된 노드들은 부모 or 자식 노드이다.
- 탐색 시, 이미 방문한 노드가 나오면 현재 노드의 부모노드이므로 넘어간다.
- 탐색 시, 방문한적이 없다면 자식노드이다.
전체 코드
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
//연결리스트 선언
ArrayList<ArrayList<Integer>> tree = new ArrayList<>();
for (int i = 0; i <= n; i++) tree.add(new ArrayList<Integer>());
//출력에 사용할 부모노드 선언
int[] parent = new int[n+1];
//탐색에 사용할 체크 배열 선언
boolean[] ch = new boolean[n+1];
//부모 자식간 구분없이 입력이 들어온다. 따라서 양방향으로 입력 받는다.
for(int i=0; i<n-1; i++){
int node1 = scanner.nextInt();
int node2 = scanner.nextInt();
tree.get(node1).add(node2);
tree.get(node2).add(node1);
}
//큐를 이용해 탐색 진행
Queue<Integer> queue = new LinkedList<>();
//가장 먼저 루트 노드(1번)을 큐에 넣는다.
ch[1] = true;
queue.offer(1);
while(!queue.isEmpty()){
//현재 노드가 부모 노드. 이전에 탐색 된적이 없기 때문이다.
Integer parentNode = queue.poll();
//자식 노드를 탐색한다.
for (Integer connectedNode : tree.get(parentNode)) {
//이미 방문했다면, 자식 노드가 아니다.
if(ch[connectedNode]) continue;
else{
//자식 노드라면,
//재방문을 막기 위해 방문을 체크한다.
ch[connectedNode] = true;
//자식 노드의 부모노드 저장
parent[connectedNode] = parentNode;
//자식 노드를 큐에 넣는다.
queue.add(connectedNode);
}
}
}
for(int i=2; i<=n; i++){
System.out.println(parent[i]);
}
}
}
Author And Source
이 문제에 관하여([백준] 11725 트리의 부모 찾기(Java)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ash753/백준-11725-트리의-부모-찾기Java저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)