[백준 11725] 트리의 부모 찾기
https://www.acmicpc.net/problem/11725
1. 아이디어
알고리즘을 공부해 본 사람이라면 위 문제를 보고 쉽게 dfs 알고리즘을 생각할 수 있을 것이다. 그러나, 아직 알고리즘 문제 해결 방법에 대해 익숙하지 않아 엉뚱한 길로 빠졌다.
위 문제의 입력 예제를 바탕으로 트리를 표현해보았는데, 이게 화근이었다. 여기서 이진 트리의 늪에 빠져 헤어나오지 못했다. 그래도 접근한 방법을 버리기엔 좀 아까워서 결국 dfs로 해결하긴 했지만 어거지로 Node와 Tree를 나름 구현해보았다..
풀었던게 아까우니 아래 접근 방법에 대해 조금 끄적여 보겠다.
1-1. 기존코드
<Node 클래스>
class Node {
private int val;
private Node parent;
private ArrayList<Node> children;
public Node(int val) {
this.val = val;
this.parent = null;
this.children = new ArrayList<>();
}
public int getVal() {
return val;
}
public Node getParent() {
return parent;
}
public void setParent(Node parent) {
this.parent = parent;
}
public ArrayList<Node> getChildren() {
return children;
}
public void addChild(Node child) {
children.add(child);
child.setParent(this);
}
}
각 노드의 값, 부모 정보, 자식 정보를 저장하고자 노드 클래스를 생성했다.
<Tree 클래스>
class Tree {
private Node root;
private Node[] nodes;
public Tree(int size) {
nodes = new Node[size + 1];
for (int i = 1; i <= size; i++) {
nodes[i] = new Node(i); // 1 ~ N 까지 노드 생성
}
root = nodes[1];
}
// 부모 노드에 자식 노드 삽입
public void add(int parentVal, int childVal) {
// 루트 노드는 무조건 1
if (parentVal == 1 || childVal == 1) {
if (parentVal == 1) {
nodes[1].addChild(nodes[childVal]);
} else {
nodes[1].addChild(nodes[parentVal]);
}
return;
}
// parentVal이 트리에 이미 포함된 경우
if (nodes[parentVal].getParent() != null || !nodes[parentVal].getChildren().isEmpty()) {
if (nodes[childVal].getParent() == null) {
nodes[parentVal].addChild(nodes[childVal]);
}
}
// childVal이 트리에 이미 포함된 경우
else if (nodes[childVal].getParent() != null || !nodes[childVal].getChildren().isEmpty()) {
if (nodes[parentVal].getParent() == null) {
nodes[childVal].addChild(nodes[parentVal]);
}
}
// 둘 다 트리에 포함되지 않은 경우, 작은 값을 부모로 설정
else {
if (parentVal < childVal) {
nodes[parentVal].addChild(nodes[childVal]);
} else {
nodes[childVal].addChild(nodes[parentVal]);
}
}
}
public int getParentVal(int childVal) {
return nodes[childVal].getParent().getVal();
}
}
트리에 노드를 추가하며 조건에 맞게끔 삽입 규칙을 생성했다.
1. 입력 노드(a b) 중 1이 있다면 무조건 나머지 노드를 1의 자식노드로 설정
2. 입력 노드(a b) 중 트리에 포함된 노드가 있다면 나머지 노드를 트리에 포함된 노드의 자식으로 설정
3. 둘 다 트리에 포함되지 않은 경우, 둘 중 작은 값을 부모 노드로 설정
그 후 main에서 트리를 생성하고 N=2 부터 N까지 부모 노드를 출력했을 때, 백준의 테스트 케이스는 통과하였으나 수 많은 반례가 있었다...
먼저 위와 같이 코드를 작성하면 양방향 그래프가 아니므로, 입력이 반대로 되었을 경우에 제대로된 트리가 생성되지 않는 경우가 있었다. 또한 트리가 이어지도록 작성하는 경우 말고, 노드 (1 - 2) 생성 -> 노드 (4 - 3) 생성 -> 노드 (4 - 1) 생성 과 같이 부모 노드 탐색이 모호해지는 경우에는 제대로 된 결과를 내지 못했다... 따라서 위 방법은 포기하고 dfs 탐색을 사용하기로 했다.
1-2. 수정된 코드
<Node 클래스>
class Node {
private int val;
private ArrayList<Node> children; // 자식노드 -> ArrayList에 저장
public Node(int val) {
this.val = val;
this.children = new ArrayList<>();
}
public int getVal() {
return val;
}
public ArrayList<Node> getChildren() {
return children;
}
// 자식노드 ArrayList에 저장
public void addChild(Node child) {
children.add(child);
}
}
<Tree 클래스>
// 트리
class Tree {
private Node[] nodes; // 노드 정보 기록
private int[] parent; // 부모 노드 정보 기록
// 트리 생성 (1 ~ N)
public Tree(int size) {
nodes = new Node[size + 1]; // 1 ~ N 까지
parent = new int[size + 1]; // 각 노드 부모 저장
for (int i = 1; i <= size; i++) {
nodes[i] = new Node(i);
parent[i] = -1; // 부모 초기화
}
}
// 입력 노드 2개 양방향 트리(그래프)로 추가
public void add(int parentVal, int childVal) {
nodes[parentVal].addChild(nodes[childVal]);
nodes[childVal].addChild(nodes[parentVal]);
}
// 부모 찾기 DFS 탐색
public void dfs(int nodeVal) {
for (Node child : nodes[nodeVal].getChildren()) {
if (parent[child.getVal()] == -1) { // 부모 없으면
parent[child.getVal()] = nodeVal; // 현재 노드를 부모로
dfs(child.getVal()); // 연관된 노드 dfs 탐색
}
}
}
// 부모 값 반환
public int getParent(int nodeVal) {
return parent[nodeVal];
}
}
위 두 코드를 보면, 우선 노드에서 parent를 삭제했다. 부모 노드 추적을 Tree 클래스 안에서 parent 배열로 대신하면 되기 때문이다.
이후 Tree 클래스에서 각 노드와 부모 정보 배열을 생성 및 초기화 한다. 기존 코드에서 수정한 것인지라, add 메서드의 매개변수가 저렇게 표시되어 있지만, 사실 parentVal, childVal 이란 변수명은 틀린 의미이다.
기존의 문제점이었던 트리의 노드를 양방향으로 설정하고, dfs 탐색을 통해 부모 노드를 탐색한다.
* 여기서의 자식노드들이 dfs 의 인접 리스트로 생각하면 된다.
해당 노드와 연관된 노드들을 차례로 탐색하며 부모 노드 배열에 값을 저장하고, 추후 부모 노드 배열의 값을 출력한다.
다음부턴 이상한데 꽂히지 말고, 필히 dfs를 떠올리도록 하겠다...
2. 코드
package IntStudy;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
// 노드
class Node {
private int val;
private ArrayList<Node> children; // 자식노드 -> ArrayList에 저장
public Node(int val) {
this.val = val;
this.children = new ArrayList<>();
}
public int getVal() {
return val;
}
public ArrayList<Node> getChildren() {
return children;
}
// 자식노드 ArrayList에 저장
public void addChild(Node child) {
children.add(child);
}
}
// 트리
class Tree {
private Node[] nodes; // 노드 정보 기록
private int[] parent; // 부모 노드 정보 기록
// 트리 생성 (1 ~ N)
public Tree(int size) {
nodes = new Node[size + 1]; // 1 ~ N 까지
parent = new int[size + 1]; // 각 노드 부모 저장
for (int i = 1; i <= size; i++) {
nodes[i] = new Node(i);
parent[i] = -1; // 부모 초기화
}
}
// 입력 노드 2개 양방향 트리(그래프)로 추가
public void add(int parentVal, int childVal) {
nodes[parentVal].addChild(nodes[childVal]);
nodes[childVal].addChild(nodes[parentVal]);
}
// 부모 찾기 DFS 탐색
public void dfs(int nodeVal) {
for (Node child : nodes[nodeVal].getChildren()) {
if (parent[child.getVal()] == -1) { // 부모 없으면
parent[child.getVal()] = nodeVal; // 현재 노드를 부모로
dfs(child.getVal()); // 연관된 노드 dfs 탐색
}
}
}
// 부모 값 반환
public int getParent(int nodeVal) {
return parent[nodeVal];
}
}
// [백준_11725] 트리의 부모 찾기
public class B_11725 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// N 입력
int N = Integer.parseInt(br.readLine());
Tree tree = new Tree(N);
for (int i = 0; i < N-1; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int parentVal = Integer.parseInt(st.nextToken());
int childVal = Integer.parseInt(st.nextToken());
tree.add(parentVal, childVal);
}
// root 부터 부모 탐색
tree.dfs(1);
for(int i=2; i<=N; i++) {
System.out.println(tree.getParent(i));
}
}
}