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

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

 

dfs나 bfs로 풀면 금방 풀 수 있는 문제 같았다. 근데 오랜만에 상하좌우로 탐색하는 게 아니라 데이터를 ArrayList 배열에 저장해서 푸는 문제였어서 처음 입력 받는 걸 헤맸다. ArrayList가 Integer 형태로 받아서 for문에서 크기 비교가 안됐었는데 크기 비교할 필요 없이 array[x] 내에 있는 값을 가져오면 되는 거였어서 for(int i: array[x]) 이런 식으로 구현하면 됐었다. 예를 들어 가장 처음에 루트 노드인 1이 들어간다면, 예시로 1 4 를 입력 받고 있었으니, visited[1]은 true가 되며 i는 4가 되고, 그럼 visited[4]는 방문하지 않았으니 parent[4]는 1이 되는 방식으로 구현한 것이다. 그 다음에는 4를 부모로 갖는 노드를 찾아서 차례로 저장하는 방식이다.

 

이 문제는 다음에 다시 풀어보자!

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

public class Main {
    static boolean[] visited;
    static int[] parent;
    static ArrayList<Integer> array[]; //ArrayList 배열
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        int t = Integer.parseInt(br.readLine());
        array = new ArrayList[t+1]; // ArrayList 배열 개수
        for(int i = 0; i < t+1; i++){
            array[i] = new ArrayList<>(); // ArrayList 배열 내 ArrayList 저장
        }
        visited = new boolean[t+1];
        parent = new int[t+1];

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

        dfs(1);
        for(int i = 2; i < t+1; i++){
            bw.write(String.valueOf(parent[i])+ "\n");
        }
        bw.flush();
        bw.close();
    }

    static void dfs(int x){
        visited[x] = true;
        for(int i: array[x]){
            if(!visited[i]){
                parent[i] = x;
                dfs(i);
            }
        }
    }
}