on
[백준] 자바 11725 트리의 부모 찾기
[백준] 자바 11725 트리의 부모 찾기
문제
루트 없는 트리가 주어진다. 이때, 트리의 루트를 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
입력 3
5
1 4
2 3
4 5
1 2
출력 3
1
2
1
4
접근
1. n을 입력 받음
2. n만큼 관계를 입력 받음
3.dfs를 이용해서 1부터 입력받은 관계들을 이용해 부모 자식관계를 설정합니다.
4. 부모 배열을 출력해줍니다.
3번 과정을 더 자세히 설명하자면,
노드 1부터 시작해서, 1과 연결된 노드들을 사용합니다.
예를 들어 1에 4,6이 연결되어 있다면 부모 배열[4]과 부모 배열[6]을 1로 설정하는 것입니다.(4번 노드와 6번 노드의 부모가 1이라는 뜻의 데이터)
그리고 다시 dfs(4), dfs(6)을 호출하는 방식으로 작동합니다.
이러면 1 3, 3 1 같이 관계가 중복되는 경우가 생기는데, 이는 visit배열을 이용해서 방문하지 않은 곳만 부모 배열 값을 바꿀 수 있게 허용하면 됩니다.
코드
import java.util.*; import java.io.*; class Main { static int n; static ArrayList[] list; static int parent[]; static boolean visit[]; static void dfs(int start) { visit[start] = true; for(int i=0; i(); } for(int i=0; i
")); } br.close(); bw.flush(); bw.close(); } }
주의
x
728x90
반응형
from http://kjs-dev.tistory.com/169 by ccl(A) rewrite - 2021-11-02 09:28:36