백준 11725 트리의 부모 찾기 (JAVA 자바 풀이)
문제
루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.
출력
첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.
💡 풀이 과정
트리는 인접 행렬과 인접 리스트를 통해 구현할 수 있는데 문제에서 N의 개수가 최대 10만이다. 인접 리스트로 구현하면 10만 x 10만 = 100만의 공간을 차지하게 되므로 메모리가 4바이트라고 할 때 40기가의 메모리를 필요하므로 현재 문제에서는 사용할 수 없다.
인접 리스트를 통해 풀어보자.
먼저 인접리스트를 생성하고 행과 열에 대해서 주어진 노드를 할당해준다. 이때 행은 N 번째 노드에 대한 고정적인 공간을 할당된 것으로 배열로 구현을 해도 되지만 헷갈리지 않도록 리스트로 구현하였다.
List<List<Integer>> adjList = new ArrayList<>();
for (int i = 0; i <= N; i++) {
adjList.add(new ArrayList<>());
}
결론적으로 나오는 모양은 다음과 같은데
1 -> 6 4
2 -> 4
3 -> 6 5
4 -> 1 2 7
5 -> 3
6 -> 1 3
7 -> 4
이는 1번 노드에 연결된 노드는 6, 4
2번 노드는 4
3번 노드는 6, 5
...
임을 의미한다.
문제의 예제 노드들을 그려보면 다음과 같다.
1번 루트 노드를 기준으로 위와 같은 트리가 생성될 것이다.
인접 리스트로 표현된 1 -> 6 4 는 1번 노드와 연결된 노드가 6과 4임을 의미한다.
이를 코드에서 살펴보면 순차적으로 진행되는 i에 대해서, 그에 맞는 노드들을 채워주면 된다. 이때 현재 문제에서 단순하게 숫자를 사용된 정점 정보만 주어지고 있기 때문에 굳이 클래스를 만들 필요는 없다. cost와 방향이 주어지면 Node를 클래스로 만들어서 Integer 부분에 넣어서 생성하는 부분이 달라질 것이다.
for (int i = 0; i < N - 1; i++) {
stringTokenizer = receiveInput(bufferedReader);
int a = Integer.parseInt(stringTokenizer.nextToken());
int b = Integer.parseInt(stringTokenizer.nextToken());
adjList.get(a).add(b);
adjList.get(b).add(a);
}
리스트에 초기화된 모습은 다음과 같다.
이제 이 노드들 각각에 대해 부모 노드를 찾는 알고리즘을 구현해보자.
이제 1번 노드부터 부모를 찾아서 매핑을 할 것인데, 먼저 이미 탐색한 노드는 재방문 하지 않도록 방문 체크 배열을 사용할 수 있도록 초기화를 해둔다. 또한 방문시마다 부모를 찾았으면 이를 기록해주어야 하므로 부모 배열도 초기화를 한다.
parents = new int[N + 1];
visited = new boolean[N + 1];
그 다음 DFS를 이용해 재귀적으로 1번 노드부터 탐색을 하면서 부모노드를 찾는다.
이때, 어떻게 각 노드를 방문하는 것으로 부모 노드를 찾을 수 있는 것일까?
다음과 같은 작동 원리 때문이다.
- 트리 구조에서 한 노드는 오직 하나의 부모 노드만을 갖는다.
- DFS를 사용하여 트리를 탐색할 때, 노드를 처음 방문하는 순간에 그 노드의 부모는 DFS 호출을 한 노드입니다.
트리의 루트(가장 위에 있는 노드)에서 시작해 아래로 내려가며 각 노드를 방문한다고 생각해 보자. 루트 노드에서 시작해, 첫 번째 자식 노드로 내려간다. 이 자식 노드는 방금 방문한 루트 노드가 부모 노드이다. 다시, 이 자식 노드에서 그의 자식 노드로 내려가면, 이 노드의 부모는 방금 방문한 노드가 된다.
즉, 우리가 트리를 탐색하면서 내려갈 때마다, 방문하는 노드의 바로 전 노드가 그 노드의 부모가 되는 것이다. 이런 방식으로 트리를 탐색하면, 각 노드의 부모를 알 수 있다.
이 과정에서 중요한 것은, 한 번 방문한 노드는 다시 방문하지 않는다는 것이다. 왜냐하면, 트리 구조에서 한 노드는 오직 하나의 부모만 가지고, 한 번 방문했다는 것은 이미 그 노드의 부모를 찾았다는 의미이기 때문이다.
이 과정을 `findParents` 함수를 통해 수행해 보자. 이 함수는 현재 노드를 방문하고, 그 인접 노드들을 확인할 것이다. 따라서 방문 즉시 방문 배열에 체크한다.
// 현재 노드를 방문 처리
visited[currentNode] = true;
이후, 해당 노드의 인접 노드들에 대해서 ( 예를 들어 1-> 6 4) 각각 반복문을 돌면서, 아직 방문하지 않은 인접 노드를 발견하면, 그 노드의 부모를 현재 노드로 설정하고, 그 인접 노드를 또 방문한다. 이 경우 6을 방문 하고, 4의 차례에 오기 전에 6 이하의 노드들 (1, 3)을 방문하게 될 것이다. 그렇게 되면 1은 방문을 했으니까 3 입장에서 6을 또 부모 배열에 추가하게 된다. 3 역시 마찬가지로 6, 5를 탐색하고, 5에서 3을 부모 배열에 부모러 기록한다. 더 이상 갈 곳이 없으므로 리턴되면서 나오면, 재귀를 시작한 지점으로 다시 돌아와서 아까 도달하지 못한 4의 차례에 도달한다. 이 과정을 모든 노드에 대해 반복하여 각 노드의 부모 배열이 기록되면서 모든 노드의 부모를 찾을 수 있다.
이와 같은 인접리스트의 각 노드의 인덱스와 재귀 호출의 프로세스가 진행되는 과정을 스텝 바이 스텝으로 살펴보면 다음과 같다.
1. 노드 1 방문: 루트 노드인 1번을 방문한다. visited[1]을 true로 설정한다.
- 인접 노드: 6, 4
2. 노드 6 방문: 노드 6으로 이동. parents[6] = 1로 설정하고, visited[6]을 true로 설정한다.
- 인접 노드: 1(이미 방문함), 3
3. 노드 3 방문: 노드 3으로 이동. parents[3] = 6으로 설정하고, visited[3]을 true로 설정한다.
- 인접 노드: 6(이미 방문함), 5
4. 노드 5 방문: 노드 5로 이동합니다. parents[5] = 3으로 설정하고, visited[5]을 `true로 설정한다.
- 인접 노드: 3(이미 방문함)
5. 노드 5에서 더 이상 방문할 인접 노드가 없으므로, 노드 3으로 돌아간다.
6. 노드 3에 더 이상 방문할 인접 노드가 없으므로, 노드 6으로 돌아간다.
7. 노드 6에 더 이상 방문할 인접 노드가 없으므로, 노드 1로 돌아간다.
8. 노드 4 방문: 노드 4로 이동. parents[4] = 1으로 설정하고, visited[4]을 true로 설정.
- 인접 노드: 1(이미 방문함), 2, 7
9. 노드 2 방문: 노드 2로 이동. parents[2] = 4로 설정하고, visited[2]을 true로 설정.
- 인접 노드: 4(이미 방문함)
10. 노드 2에서 더 이상 방문할 인접 노드가 없으므로, 노드 4로 돌아간다.
11. 노드 7 방문: 노드 7로 이동. parents[7] = 4로 설정하고, visited[7]을 true로 설정.
- 인접 노드: 4(이미 방문함)
12. 노드 7에서 더 이상 방문할 인접 노드가 없으므로, 노드 4로 돌아간다.
13. 노드 4에 더 이상 방문할 인접 노드가 없으므로, 노드 1로 돌아간다.
14. 노드 1에 더 이상 방문할 인접 노드가 없으므로, 탐색을 종료한다.
이를 간단히 시각화 하면 다음과 같다.
트리의 부모 찾기 알고리즘
├── 초기 설정
│ ├── 인접 리스트 생성 (List<List<Integer>> adjList)
│ └── 노드 연결 정보 입력
│ └── adjList에 각 노드 연결 정보 추가
├── 부모 노드 찾기
│ ├── 방문 체크 배열 초기화 (boolean[] visited)
│ ├── 부모 노드 배열 초기화 (int[] parents)
│ └── DFS 수행 (findParents 함수)
│ ├── 노드 1 방문 (루트 노드)
│ │ └── 인접 노드 탐색 (6, 4)
│ │ ├── 노드 6 방문
│ │ │ └── 인접 노드 탐색 (1, 3)
│ │ │ └── 노드 3 방문
│ │ │ └── 인접 노드 탐색 (6, 5)
│ │ │ └── 노드 5 방문
│ │ └── 노드 4 방문
│ │ └── 인접 노드 탐색 (1, 2, 7)
│ │ ├── 노드 2 방문
│ │ └── 노드 7 방문
└── 결과 출력
└── 부모 노드 번호 출력 (2번 노드부터 순서대로)
💡 코드 구현
import static java.lang.Integer.*;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
private static List<List<Integer>> adjList;
private static int[] parents;
private static boolean[] visited;
private static StringTokenizer receiveInput(BufferedReader bufferedReader) throws IOException {
return new StringTokenizer(bufferedReader.readLine());
}
public static void main(String[] args) throws IOException {
// BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
BufferedReader bufferedReader = new BufferedReader(new FileReader("input.txt"));
StringTokenizer stringTokenizer = receiveInput(bufferedReader);
int N = parseInt(stringTokenizer.nextToken());
adjList = new ArrayList<>();
for (int i = 0; i <= N; i++) {
adjList.add(new ArrayList<>());
}
for (int i = 0; i < N - 1; i++) {
stringTokenizer = receiveInput(bufferedReader);
int a = Integer.parseInt(stringTokenizer.nextToken());
int b = Integer.parseInt(stringTokenizer.nextToken());
adjList.get(a).add(b);
adjList.get(b).add(a);
}
parents = new int[N + 1];
visited = new boolean[N + 1];
findParents(1);
for (int i = 2; i <= N; i++) {
System.out.println(parents[i]);
}
}
private static void findParents(int currentNode) {
// 현재 노드를 방문 처리
visited[currentNode] = true;
// 인접 리스트를 순회
for (int adjacent : adjList.get(currentNode)) {
// 인접 노드가 방문되지 않았다면
if (!visited[adjacent]) {
// 인접 노드의 부모를 현재 노드로 설정
parents[adjacent] = currentNode;
// 인접 노드를 방문
findParents(adjacent);
}
}
}
}
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 5397 키 로거 (JAVA 자바 풀이) (0) | 2024.01.03 |
|---|---|
| 백준 2118 두 개의 탑 (JAVA 자바 풀이) (1) | 2024.01.02 |
| 백준 15653 N과 M (5) (JAVA 자바 풀이) (2) | 2023.12.31 |
| 백준 2504 괄호의 값 (JAVA 자바 풀이) (1) | 2023.12.31 |
| 백준 1406 에디터 (JAVA 자바 풀이) (0) | 2023.12.28 |
