[백준] #11725 트리의 부모찾기 (BFS/DFS)

 

https://www.acmicpc.net/problem/11725

11725번: 트리의 부모 찾기

---

✅ 문제 이해하기

둘째 줄부터 주어지는 두 노드는 방향성이 없는 연결된 노드이다.

이런 노드들을 모두 연결했을 때 아래와 같은 그림이 되고, 이를 트리를 바꿔서 볼 수 있다.

따라서 우리는 다음과 같은 과정을 거쳐야 한다.

1. 주어진 두 노드의 연결관계를 그리고
2. 모든 노드를 순회하면서 각 노드의 부모가 누구인지를 알아내야한다

 

✅ 문제 해체하기

 

1. 주어진 두 노드의 연결관계 그리기/나타내기

우리가 그릴 트리는 방향성이 없다는 것을 기억해두고,

각 노드들을 기준으로 어떤 노드와 연결되어있는지를 모두 기록해주어야한다.

예를 들어, ( 1 6 ) 으로 값이 들어왔다면

1. 1번 노드는 6번 노드와 연결되어있음
2. 6번 노드는 1번 노드와 연결되어있음

이렇게 정리를 해주어야하기 때문에 ArrayList<ArrayList<Integer>> 로 노드 간 연결을 추가해준다.

2. 모든 노드를 순회하면서 각 노드의 부모가 누구인지를 알아내야 한다.

우리가 노드를 순회할 수 있는 방법은 2가지가 있다.

1. BFS (너비우선탐색)
2. DFS (깊이우선탐색)

이때 두 탐색 방법 모두 공통으로 가지는 Point 가 있다

💡 연결된 노드를 방문할 때, 방문한 적이 있다면 부모 노드이다.

 

이게 무슨 의미인지 이해하기 어려울 수 있다 (필자가 그랬다,,)

그래서 첫 번째 예제를 그림으로 그려본 다음 이해해보려고 한다.

 

1. BFS (너비우선탐색)

; 루트 노드를 시작으로, 인접한 노드 순으로 탐색
= 정점으로부터 가까운 정점을 먼저 방문하며, 멀리 있을수록 가장 나중에 방문하는 형태

 

가장 먼저 루트 노드인 1에서 인접한 노드를 접근했을 때,
(당연히 1은 루트노드이기 때문에 연결된 노드의 부모노드이지만 규칙을 보자면)

4번 노드는 방문한 적이 없다6번 노드는 방문한 적이 없다
= 4번과 6번 둘 중 하나를 거쳐서 1번 노드에 도달한 적이 없다

따라서 1은 4, 6번의 부모 노드가 된다.

 

다음으로 인접해있던 6번 노드를 보았을때, 인접한 노드는 1, 3번 노드이다.

1번 노드는 방문한 적이 있다 (부모노드)
3번 노드는 방문한 적이 없다
= 3번 노드를 거쳐서 6번 노드에 접근한 적이 없다

따라서 6번은 3번의 부모 노드가 된다.

 

이런 방식으로 연결된 노드들에 대한 부모를 찾아나간다.

이를 코드로 바꿔서 생각할 때, 인접한 노드에 대한 정보는 큐에 저장해서 관리하면 된다.

 

 

2. DFS (깊이우선탐색)

; 루트 노드를 시작으로, 하나의 브랜치의 끝까지 탐색 후 다음 브랜치로 넘어감
= 정점과 연결된 마지막 노드를 만날 때까지 계속 순환하며 탐색함

 

아까와 같이 주어진 첫 번째 예제로 그림을 그려보면 다음과 같다

 

이를 조금 더 풀어서 보면

---

루트 노드 1에서 시작, 노드 1과 연결된 노드 4와 6에서

1. 노드 6은 방문한 적이 없음
   1. → 연결된 노드 1, 3 확인
      1. 연결된 노드 1은 방문한 적이 있음 = pass
      2. 연결된 노드 3은 방문한 적이 없음
         1. → 연결된 노드 5 확인
            1. 연결된 노드 5는 방문한 적이 없음
               1. → 연결된 노드 확인, 연결된 노드 없음 = 5의 부모 노드는 
         2. 연결된 노드 모두 확인, 3의 부모 노드는 6
         2.  연결된 노드 모두 확인, 노드 6의 부모노드는 1
2. 노드 4는 방문한 적이 없음
   1. → 연결된 노드 1, 2, 7 확인
      1. 연결된 노드 1은 방문한 적이 있음 = pass
      2. 연결된 노드 2는 방문한 적이 없음
         1. → 연결된 노드 확인. 연결된 노드 없음 = 2의 부모노드는 4
      3. 연결된 노드 7은 방문한 적이 없음
      4. → 연결된 노드 확인, 연결된 노드 없음 = 7의 부모 노드는 4
   2. 연결된 노드 모두 확인. 노드 4의 부모노드는 1

---

이렇게 재귀적으로 연결된 노드를 찾아가, 그 끝에 도달했을 때 부모 노드를 기록할 수 있다

이를 코드로 바꿔서 생각해본다면 다음과 같을 것이다.

 

 

✅ 코드

 

먼저 노드 개수 N을 받아온 다음 , 노드 간 연결을 관리할 리스트에 넣어주어야 한다

그리고 노드를 방문했는지 기록할 배열과, 각 노드의 부모를 기록할 배열을 생성한다.

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());

for (int i=0; i<=n; i++) { // 루트를 1이라고 설정했기 때문에, 편의상 1부터 N으로 관리하기 위해 0부터 N까지 생성
   nodes.add(new ArrayList<>()); // 연결된 노드 값들을 넣기 위해 ArrayList 로 생성
}

for (int i=1; i<n ; i++) { // 첫째줄부터 N-1번째 줄까지
    String[] arr = br.readLine().split(" ");
    int node1 = Integer.parseInt(arr[0]);
    int node2 = Integer.parseInt(arr[1]);

    nodes.get(node1).add(node2); // node1에 대해 연결된 노드 값으로 node2 추가
    nodes.get(node2).add(node1); // node2에 대해 연결된 노드 값으로 node1 추가
}

visited = new boolean[n+1]; // 0~n까지 만들었기 때문에 n+1개 필요
parents = new int[n+1]; // 0~n까지 만들었기 때문에 n+1개 필요

 

1. BFS

인접한 노드를 넣어둘 큐를 생성한 뒤,

루트 노드 1에서 시작할 것이기 때문에 큐에 1을 추가하고, visited 를 true(방문했음)로 할당한다.

Queue<Integer> queue = new LinkedList<>();
queue.add(1); // 루트 노드 값
visited[1] = true;

 

이 후로, 큐에 있는 값을 차례대로 꺼내면서 연결된 노드에 대해서 확인한다.

만약 방문한 적이 없는 노드라면 큐에 값을 추가하고, 큐에서 꺼낸 값이 부모 노드가 된다.

while(!queue.isEmpty()){
    int p = queue.remove(); // 큐에서 처음 값을 꺼내옴
    for(int c : nodes.get(p)){ // 꺼내온 값과 연결된 노드들을 탐색
        if(!visited[c]){ // 방문한 적 없는 노드 == 자식 노드
            visited[c] = true;
            queue.add(c);
            parents[c] = p;
        }
    }
}

 

큐에 값이 들어가고, remove 되는 과정을 명시적으로 보면 다음과 같다

 

2. DFS

우선, 노드에 방문했음을 나타내고 해당 노드와 연결된 노드들을 탐색한다

만약 방문하지 않았던 노드라면 부모가 아니기 때문에, 연결된 노드를 찾아 들어간다

이후, 연결된 노드가 더이상 없다면 순차적으로 부모 노드를 기록하며 올라온다

static void DFS(int p) {
        visited[p] = true; // 노드에 방문했음을 표시
    for (int c : nodes.get(p)) {
        if (!visited[c]) {

          // 방문했던 노드를 만날 때까지 깊이 탐색 
                    DFS(c); 

                    // 방문했던 노드를 만나면 재귀함수 탈출
                    parents[c] = p;
        }
    }
}

 

✅ 전체 코드

BFS

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        ArrayList<ArrayList<Integer>> nodes = new ArrayList<ArrayList<Integer>>();
        for (int i=0; i<=n; i++) { // 루트를 1이라고 설정했기 때문에, 편의상 1부터 N으로 관리하기 위해 0부터 N까지 생성
            nodes.add(new ArrayList<>()); // 연결된 노드 값들을 넣기 위해 ArrayList 로 생성
        }

        for (int i=1; i<n ; i++) { // 첫째줄부터 N-1번째 줄까지
            String[] arr = br.readLine().split(" ");
            int node1 = Integer.parseInt(arr[0]);
            int node2 = Integer.parseInt(arr[1]);

            nodes.get(node1).add(node2); // node1에 대해 연결된 노드 값으로 node2 추가
            nodes.get(node2).add(node1); // node2에 대해 연결된 노드 값으로 node1 추가
        }

        boolean[] visited = new boolean[n+1]; // 0~n까지 만들었기 때문에 n+1개 필요
        int[] parents = new int[n+1]; // 0~n까지 만들었기 때문에 n+1개 필요

        // BFS
        Queue<Integer> queue = new LinkedList<>();
        queue.add(1);
        visited[1] = true;
        while(!queue.isEmpty()){
            int p = queue.poll();
            for(int c : nodes.get(p)){
                if(!visited[c]){
                    visited[c] = true;
                    queue.add(c);
                    parents[c] = p;
                }
            }
        }

        for (int i=2; i<parents.length; i++) { // 노드 2부터 n까지 부모 출력
            System.out.println(parents[i]);
        }
    }
}

 

DFS

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

public class Main {
    static ArrayList<ArrayList<Integer>> nodes = new ArrayList<>();
    static boolean[] visited;
    static int[] parents;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        for (int i=0; i<=n; i++) { // 루트를 1이라고 설정했기 때문에, 편의상 1부터 N으로 관리하기 위해 0부터 N까지 생성
            nodes.add(new ArrayList<>()); // 연결된 노드 값들을 넣기 위해 ArrayList 로 생성
        }

        for (int i=1; i<n ; i++) { // 첫째줄부터 N-1번째 줄까지
            String[] arr = br.readLine().split(" ");
            int node1 = Integer.parseInt(arr[0]);
            int node2 = Integer.parseInt(arr[1]);

            nodes.get(node1).add(node2); // node1에 대해 연결된 노드 값으로 node2 추가
            nodes.get(node2).add(node1); // node2에 대해 연결된 노드 값으로 node1 추가
        }

        visited = new boolean[n+1]; // 0~n까지 만들었기 때문에 n+1개 필요
        parents = new int[n+1]; // 0~n까지 만들었기 때문에 n+1개 필요

        DFS(1); // 주어진 루트 노드 1 부터 시작 -> 모든노드를 순회하며 parents 값을 찾음

        // dfs 를 통해 찾은 parents 값들 출력,
        for (int i=2; i<parents.length; i++) { // 노드 2부터 n까지 부모 출력
            System.out.println(parents[i]);
        }
    }

    static void DFS(int p) {
        visited[p] = true; // 노드에 방문했음을 표시
        for (int c : nodes.get(p)) {
            if (!visited[c]) {
                DFS(c); // 방문했던 노드를 만날 때까지 깊이 탐색
                // 방문했던 노드를 만나면 재귀함수 탈출
                parents[c] = p;
                // 노드 c의 부모 노드는 p
            }
        }
    }
}

 

✅ 내가 생각한 방법

 

트리와 BFS / DFS 를 안다면 기본적인 문제였겠지만,

해당 개념을 모른다면 정말 어떻게 풀어야할지 막막할 문제이다.

앞으로 자주 나올 문제풀이 방법이기 때문에 개념을 공부하자!

 

[알고리즘] 너비 우선 탐색(BFS)이란 - Heee's Development Blog

 

[알고리즘] 깊이 우선 탐색(DFS)이란 - Heee's Development Blog

 

✅ 참고 자료

velog

 

velog

 

Java 백준 문제풀이 (30) 11725: 트리의 부모 찾기