[Silver_II] 백준 - 11725. 트리의 부모 찾기 : Java

11725번: 트리의 부모 찾기

 

 

 

 

 

이해하기

• root 노드는 항상 1
• 첫째 줄의 수는 노드의 총 개수 (root 노드 포함)
• 1 6 과 같은 형식의 입력은 1번 노드와 6번 노드가 연결되어 있음을 의미

 

우리가 출력해야 하는 부분은 2~7번 노드 각각의 부모 노드들이다!

 

 

 

문제풀이

사실 이 문제는 잡고 고민하다가 도저히 길이 보이지 않아 다른 분들의 코드를 참고하며 풀었다.

알고리즘 수업을 분명 들었는데도 기억이 안 나는 magic... 내 머리 속의 지우개다.

DFS, BFS 복습을 해야겠다!!

 

 

루트 노드 1 방문

• 1의 인접한 노드는 4와 6
• 1이 루트 노드이기 때문에 4와 6은 전부 1의 자식 노드
• 즉 4와 6의 부모 노드는 1

노드 4 방문

• 4의 인접한 정점은 1, 2, 7
• 1은 이미 방문했으므로 인접한 정점을 찾는 과정에서 제외함
• 남은 2와 7은 4의 자식 노드
• 2와 7의 부모 노드는 4

이 과정을 반복하여 특정 노드의 부모 노드를 알아낼 수 있다.

 

import java.util.*;

public class no_11725 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 노드 개수 입력

        // 트리 구조 표현을 위한 그래프 구현
        ArrayList<ArrayList<Integer>> tree = new ArrayList<>();
        for (int i = 0; i < n; i++)
            tree.add(new ArrayList<>());

        // 그래프 입력
        for (int i = 0; i < n - 1; i++) {
            int n1 = sc.nextInt() - 1;
            int n2 = sc.nextInt() - 1;
            tree.get(n1).add(n2);
            tree.get(n2).add(n1);
        }

        boolean[] visited = new boolean[n]; // 방문 여부 확인용 배열
        int[] parentNode = new int[n]; // 부모 노드 저장 배열

        // BFS
        Queue<Integer> queue = new LinkedList<>();
        queue.add(0);
        visited[0] = true;
        while (!queue.isEmpty()) {
            int v = queue.remove();
            for (int node : tree.get(v))
                if (!visited[node]) {
                    visited[node] = true;
                    queue.add(node);
                    parentNode[node] = v; // 부모 노드 찾은 후 저장
                }
        }

        // 루트 노드를 제외한 나머지 노드의 부모 노드 출력
        for (int i = 1; i < n; i++)
            System.out.println(parentNode[i] + 1);
    }
}

 

 

한 줄 한 줄 분석해보자😤

 

import java.util.*;

 

매번 코테를 풀 때마다 import문을 잊어버려 문제가 생겼는데, 스터디원분께서

• import java.util.*;
• import java.io.*;

이 두 가지를 습관적으로 넣어주면 웬만한 문제는 발생하지 않는다고 알려주셨다!

 

Scanner sc = new Scanner(System.in);

 

평소라면 입력을 BufferedReader로 받았을텐데, 참고한 글에서 Scanner를 사용하셔서 사용해보았다.

(다시 풀 때는 BufferedReader로 풀어보자!)

 

int n = sc.nextInt();

 

노드의 총 개수를 받아온다.

 

ArrayList<ArrayList<Integer>> tree = new ArrayList<>();
        for (int i = 0; i < n; i++)
            tree.add(new ArrayList<>());

 

트리 구조 표현을 위한 그래프를 구현한다.

이 부분부터 조금 막혔는데, 2차원 배열과 비슷할 것 같다.

(나라면 for문에 무조건 {}를 붙였을텐데, 한 줄짜리 코드는 오히려 이렇게 작성하는 것이 더 깔끔해보인다.)

 

for (int i = 0; i < n - 1; i++) {
	int n1 = sc.nextInt() - 1;
	int n2 = sc.nextInt() - 1;
	tree.get(n1).add(n2);
	tree.get(n2).add(n1);
}

 

그래프 입력 부분이다.

트리에서 간선의 수 = 정점의 수 - 1 이기에 n - 1까지 for문을 돌린다.

n1과 n2에서 각각 -1을 해주는 이유는 노드의 값은 1~7 이지만, 실제로는 0~6 에 저장될 것이기 때문이다.

n1 = 0, n2 = 5라면 트리의 0번째 ArrayList에 5를 넣어주고 반대로 트리의 5번째 ArrayList에도 0을 넣어준다.

 

boolean[] visited = new boolean[n];

 

방문 여부를 확인하기 위한 boolean 배열을 만들어 준다.

 

int[] parentNode = new int[n];

 

부모 노드를 저장할 int 배열도 만들어 준다.

 

Queue<Integer> queue = new LinkedList<>();
queue.add(0);
visited[0] = true;
while (!queue.isEmpty()) {
    int v = queue.remove();
    for (int node : tree.get(v)) {
        if (!visited[node]) {
            visited[node] = true;
            queue.add(node);
            parentNode[node] = v;
        }
    }
}

 

가장 어려웠던 BFS 부분... (참고로 BFS는 너비 우선 탐색)

 

1. queue에 0을 add한다.
2. visited[0] = true
3. queue가 전부 비워질 때까지 while 문을 반복한다.
4. queue.remove()로 queue의 맨 첫 번째 수를 v에 대입한다.
5. tree.get(v)로 v와 연결된 정점들을 찾는다.
   1. 방문하지 않은 정점이면 visited[node] 를 true로 바꿔준다.
   2. queue에 해당 node를 add한다.
   3. parentNode 배열의 해당 node 자리에 부모 노드(v)를 저장한다.

 

for (int i = 1; i < n; i++)
	System.out.println(parentNode[i] + 1);

 

루트 노드를 제외한 나머지 노드들의 부모 노드를 출력한다.

+1을 해준 이유는 위에서 -1을 했던 이유와 같다.

 

 

 

마무리

BFS와 DFS 알고리즘에 대한 공부가 많이 부족한 걸 체감한다.

시간을 내서라도 알고리즘 강의를 복습해야겠다🥹

 

 

 

 

 

참고

[백준] 11725 : 트리의 부모 찾기 - Java

 

[백준 11725번] 트리의 부모찾기(자바)

 

[코딩테스트] 트리의 부모 찾기