처음에는 문제가 너무 이해가 안되서 천천히 그려가며 이해하는것부터 시작했다.
일단 규칙을 보니 노드의 갯수와 입력값의 수 중 가장 큰 값이 동일하고, 1부터 시작하여 N번까지 있는것을 알아차리고는 바로 그림으로 그려서 확인했다.
이러한 모습이 나와서 출력값을 보니
맨 위 출력값은
2의 부모의 값
3의 부모의 값
4의 부모의 값
...
N - 1의 부모의 값
이 출력 되어있다.
이 때 루트는 1 즉, 최상위 트리는 부모가 없기때문에,
각 숫자를 트리로 연결하고 문제해결을 해보기 시작했다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
class Main {
static ArrayList<Integer>[] graph;
static int[] parent;
static boolean[] visited;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
graph = new ArrayList[N + 1];
parent = new int[N + 1];
visited = new boolean[N + 1];
for (int i = 1; i <= N; i++) {
graph[i] = new ArrayList<>();
}
for (int i = 0; i < N - 1; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
graph[u].add(v);
graph[v].add(u);
}
dfs(1);
StringBuilder sb = new StringBuilder();
for (int i = 2; i <= N; i++) {
sb.append(parent[i]).append("\n");
}
System.out.println(sb);
}
static void dfs(int node) {
visited[node] = true;
for (int child : graph[node]) {
if (!visited[child]) {
parent[child] = node;
dfs(child);
}
}
}
}변수 선언과 초기화
- graph 는 각 노드마다 연결된 노드들을 저장하는 배열
- parent 는 각 노드의 부모를 저장하는 배열
- visited 는 각 노드의 방문 여부를 저장하는 배열
그래프 초기화 및 입력 처리
- graph 배열의 각 인덱스마다 ArrayList 를 생성하여 초기화. 이때, 노드 번호는 1부터 시작하므로 N + 1 크기로 배열을 생성해서 직관적으로 이해하기 쉽게 만듬. 이때 0번 인덱스 배열은 사용하지 않음.
- for 문을 통해 노드가 N개 이므로 N - 1 개의 간선 정보를 입력받음
- StringTokenizer 로 입력받은 후, Tokenizer 의 기본 구분자는 공백이기 때문에, 그 기준으로 분리하여 st 객체에 생성
- Integer.parsInt 와 nextToken 메서드로 u 에는 첫번째 숫자, v에는 두번째 숫자를 int 형으로 변환하여 저장
- N + 1 개의 graph 배열에 숫자를 저장. 현재 grape[0] 인덱스는 null 값이므로, 1번 인덱스부터 데이터가 들어가기 시작함
- 노드 u 에 연결된 노드 리스트에 v 를 추가
- 노드 v 에 연결된 노드 리스트에 u 를 추가
DFS 메서드
- dfs 메서드는 재귀호출하여, 특정 노드에서 시작하여 DFS를 수행.
- visited[node] 를 true 로 설정하여 현재 노드를 방문처리
- 현재 노드의 모든 자식 노드를 확인하여 방문하지 않은 노드에 대해 부모를 설정하고 재귀적으로 DFS를 호출
-parent[child] = node 를 통해 자식 노드의 부모를 현재 노드로 설정
문제를 잘 이해하지도 못했고, 풀이를 많은곳에서 검색해보고 찾아보고 풀었기 때문에 이에 대한 공부는 아직 더 필요한것 같다. 그래프와 DFS(깊이 우선 탐색) 알고리즘 , 그리고 재귀함수 쪽을 더 깊이 학습해야 할 것 같다.
Hello World