백준 11725번 (java)

백준 11725번 트리의 부모 찾기

관찰

1. 완전 탐색 - 연결 정보를 활용해 양방향 그래프로 만들고 1을 기준으로 탐색하여 해당 노드를 발견하기 전 방문한 노드가 부모 노드!
2. 최적화 - 각각의 노드를 탐색하기 위해 dfs를 돈다면 N-1번 돌아야 한다.. -> 한번의 탐색으로 그 전 노드를 기록하는 방식으로 배열에 저장 후 한번에 출력하는 방식을 사용!

정답코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main{
    static int n; // 노드의 갯수
    static ArrayList<Integer>[] graph; // 양방향 연결 그래프
    static int[] resArr; // 정답 배열
    static int[] visited; // 탐색을 위한 방문 배열
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        // 초기화
        n = Integer.parseInt(br.readLine());
        graph = new ArrayList[n+1];
        for (int i = 0; i < n + 1; i++) {
            graph[i] = new ArrayList<>();
        }
        resArr = new int[n+1];
        visited = 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());
            graph[a].add(b);
            graph[b].add(a);
        }
        // 탐색 시작
        dfs(1,0); //현재 노드와 이전 노드
        // 출력
        for (int i = 2; i < n + 1; i++) {
            sb.append(resArr[i] + "\n");
        }
        System.out.println(sb);
    }

    private static void dfs(int cur, int ex) {
        resArr[cur] = ex;
        visited[cur] = 1;
        for(int next : graph[cur]){
            if(visited[next] == 0){
                dfs(next,cur);
            }
        }
    }
}

풀이

하나하나씩 탐색하는 것이 아닌 한번의 완전탐색으로 끝내는 것이 핵심!
그리고 이렇게 출력이 많이 나오는 문제는 StringBuilder를 사용해서 시간을 많이 줄일 수 있음!

느낀점

전처리의 순한맛!