백준 - (11725)트리의 부모 찾기

---

이번 문제는 dfs 문제였다 dfs에 대해서 잘 몰랐던 나는 조금 난관을 겪었다

 

일단 트리를 그려봤다

이런식으로 트리가 만들어진다

 

문제는 루트가 없는 트리 구조에서 각 노드의 부모를 찾는 문제이다. 그리고 루트 노드는 1이다

 

2의 부모는 4

3의 부모는 6

4의 부모는 1

5의 부모는 3

6의 부모는 1

7의 부모는 4 

 

이런 식으로 출력이 나오게 만들면 된다

 

이 문제를 풀기 위해선 트리를 구성하는 노드와 엣지를 표현하고 각 노드의 부모를 찾아야 된다

노드와 엣지를 표현하기 위해 ArrayList를 사용했고 ArrayList의 각 요소는 각 노드를 나타낸다. 그리고 그 요소에 저장된 값들은 해당 노드에 연결된 이웃 노드다

 

이렇게 트리를 만들면 dfs를 사용해서 탐색해 주면 된다.

 

package S2_Baekjoon;

import java.util.*;

public class Baekjoon11725 {

    static int n; // 노드(혹은 정점)의 수
    static boolean[] visited; // 해당 노드를 방문했는지 여부를 나타내는 배열
    static ArrayList<Integer> tree[]; // 트리의 인접 리스트를 나타내는 배열
    static int answer[]; // 각 노드의 부모를 저장하는 배열

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

        // 위에서 선언한 배열들을 초기화합니다. 
        // 노드 정점의 번호가 1 부터 시작하기 때문에 n+1 크기의 배열을 생성해야된다
        visited = new boolean[n + 1];
        tree = new ArrayList[n + 1];
        answer = new int[n + 1];

        // 각 노드에 대한 인접 리스트를 초기화합니다.
        for (int i = 0; i < tree.length; i++) {
            tree[i] = new ArrayList<>();
        }

        // 노드 간의 연결 상태를 입력받습니다.
        for (int i = 1; i < n; i++) {
            int n1 = sc.nextInt();
            int n2 = sc.nextInt();
            tree[n1].add(n2);
            tree[n2].add(n1); // 양방향 그래프이므로 양 쪽 모두에 연결 정보를 추가합니다.
        }

        // DFS실행
        DFS(1);

        // 정답 출력
        for (int i = 2; i <= n; i++) {
            System.out.println(answer[i]);
        }
    }

    
    static void DFS(int number) {
        Stack<Integer> stack = new Stack<>(); // 스택 생성
        stack.push(number); // 첫 번째 노드를 스택에 넣습니다.
        visited[number] = true; // 첫 번째 노드를 방문했다고 표시합니다.
        
        while (!stack.isEmpty()) {
            int current = stack.pop(); // 스택에서 맨 위의 노드를 꺼냅니다.
            for (int i : tree[current]) { // 꺼낸 노드와 연결된 모든 노드를 확인합니다.
                // 아직 방문하지 않은 노드에 대해서만 실행합니다.
                if (!visited[i]) {
                    visited[i] = true; // 해당 노드를 방문했다고 표시합니다.
                    answer[i] = current; // 해당 노드의 부모를 현재 노드로 설정합니다.
                    stack.push(i); // 해당 노드를 스택에 넣습니다.
                }
            }
        }
    }
}

이건 스택을 이용한 문제 풀이 방법이다

static void DFS(int number) {
		visited[number] = true;
		for (int i : tree[number]) {
			if (!visited[i]) {
				answer[i] = number;
				DFS(i);
			}
		}
	}

그리고 이건 재귀를 이용한 풀이 방법이다

 

 

재귀의 풀이가 훨씬 간단해 보일 수 있으나 깊이가 매우 깊어지는 경우에는 스택 오버플로우 문제가 발생할 수 있다.

재귀 호출은 함수를 계속해서 호출하기 때문에 시스템 스택을 사용하게 되는데, 이 스택이 너무 많이 쌓이면 스택 오버플로우가 발생한다

 

스택은 코드가 좀 더 복잡해지는 대신 스택 오버플로우 문제를 피할 수 있고 스택의 사이즈를 필요에 따라 조절할 수 있다

 

 

for (int i : tree[current])

이 부분의 출력을 확인해 보자면 

이런 식으로 1 2 3 4... 순으로 tree가 저장되어 있는 걸 확인할 수 있다.

 

아무래도 dfs bfs 관련한 공부가 많이 필요할 것 같다..