문제 : [백준] 실버II_11725: 트리의 부모 찾기
🤔 문제 분석
❓문제
루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.
-> 루트없는 트리? 그런데 트리의 루트가 1?
첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.
✓ 입출력 예시
입력
7
1 6
6 3
3 5
4 1
2 4
4 7
출력
4 => 2번 노드의 부모 노드
6 => 3번 노드의 부모 노드
1 => 4번 노드의 부모 노드
3 => 5번 노드의 부모 노드
1 => 6번 노드의 부모 노드
4 => 7번 노드의 부모 노드
📝 풀이 설계
두 정점(Vertex)의 연결 간선(Edge)이 주어지고, 트리 형태로 구현하여 각 번호의 노드의 부모 노드를 출력하게 해야한다.
(1) 간선을 통해 그래프를 표현한다.
(2) 인접리스트를 이용하여 양방향 연결이 이루어지게 한다.
(3) 큐를 이용하여 위에서부터 BFS 탐색을 통해 부모노드를 저장한다.
👀 다른사람 풀이
👍 코드 해체
각 노드에 인접리스트를 생성하여, 정점 연결(양방향)을 통해 간선을 만들어 그래프를 우선 완성시키고 graph에 getParent() 메서드를 통해 BFS 탐색을하며 부모 노드의 값을 저장하는 솔루션인 것 같다.
Node 클래스
class Node {
int num;
List<Node> adjList = new ArrayList<>(); // 인접리스트
Node (int num) {
this.num = num;
}
}노드의 번호와 인접리스트를 갖고 있는 Node 클래스를 생성하셨다.
Graph 클래스
class Graph {
int N; // N개
Node[] nodes; // 노드를 담을 배열
Graph(int N) {
this.N = N;
nodes = new Node[N + 1];
for (int i = 1; i <= N; i++) {
nodes[i] = new Node(i); // 노드 초기화
}
}
void addEdge(int v1, int v2) {}
int[] getParent() {}
}노드의 개수를 담는 N과 노드들을 담는 배열 nodes가 있고, 생성할 때 N을 입력 받으면, 배열에 초기화가 되게 설계 되어 있다.
addEdge 메서드
void addEdge(int v1, int v2) {
Node n1 = nodes[v1];
Node n2 = nodes[v2];
n1.adjList.add(n2);
n2.adjList.add(n1);
}정점(Vertex) 두개를 입력 받아서 정점에 해당하는 노드를 불러오고, 각 노드 인접리스트에 서로 추가(양방향(무방향))
getParent 메서드
int[] getParent() {
Queue<Node> queue = new LinkedList<>();
queue.offer(nodes[1]); // 루트가 되는 1번 노드
boolean[] visited = new boolean[N + 1]; // 방문 여부 배열
int[] parent = new int[N + 1]; // 부모의 노드 번호 배열
while(!queue.isEmpty()) {
Node cur = queue.poll();
visited[cur.num] = true;
for (Node adj : cur.adjList) {
if (!visited[adj.num]) {
queue.offer(adj); // 큐에 추가
parent[adj.num] = cur.num; // 자식 노드 번호에 부모 노드 번호 저장
}
}
}
return parent;
}사실상 BFS 로직이다. Queue를 생성해서, 루트부터 한층씩 순회하며 방문여부와, 부모 노드의 번호를 업데이트 한다.(작성자분께서는 ArrayDeque를 사용하셨는데 이유는 모르겠다)
원래 작성하신분의 코드에선 void로 하여 바로 부모노드를 출력하였지만, 부모노드를 가져온다는 목적에 맞게 출력은 main 클래스에서 하게 수정하였다.
💪 배운점
- 트리와 그래프
- 인접리스트
- BFS
- Queue를 이용한 BFS
