📝문제

때로는 동적할당이 정적으로 초기화하는 것보다 효율이 좋다는 것을 알려준 문제!
간선의 연결정보를 크기가 100001 x 100001 인 2차원배열에 저장하니까 메모리초과가 발생했다.
처음에는 메모리초과가 이것때문에 일어나는지 몰라서 BFS방식에서 DFS방식으로 바꾸어보고
다양한 시도들을 했는데... 결국 문제는 이것때문이었다.💢

📌코드

package DFS;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class BOJ11725 {

  // 최대 사이즈인 100001 * 100001 크기의 배열을 만들면 메모리 초과 발생 -> 동적할당으로 바꿔야한다
  static int n;
  static ArrayList<Integer>[] edge; // 노드 연결 정보
  static boolean[] visited; // 방문 체크
  static int[] answers;

  static void dfs(int cur){
    // backtracking
    visited[cur] = true;

    for(int i = 0; i < edge[cur].size(); i++){
      int child = edge[cur].get(i);
      if(!visited[child]){
        answers[child] = cur;
        dfs(child);
      }
    }
  }

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    n = Integer.parseInt(br.readLine());
    StringTokenizer st;
    edge = new ArrayList[n+1];
    for(int i = 0; i < edge.length; i++){
      edge[i] = new ArrayList<>();
    }
    visited = new boolean[n+1];
    answers = new int[n+1];

    for(int i = 0; i < n-1; i++){
      st = new StringTokenizer(br.readLine());
      int a = Integer.parseInt(st.nextToken());
      int b = Integer.parseInt(st.nextToken());
      edge[a].add(b);
      edge[b].add(a);
    }

    dfs(1);

    StringBuilder sb = new StringBuilder();
    for(int i = 2; i < n+1; i++){
      sb.append(answers[i]).append("\n");
    }
    System.out.println(sb.toString());
  }
}