엘리스 알고리즘 코드 챌린지 Day4(07월 11일) - Java

문제

나의 제출(오답)

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        boolean[][] line = new boolean[N + 1][N + 1];

        for (int i = 1; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            line[a][b] = line[b][a] = true;
        }


        Queue<Game> queue = new LinkedList<>();
        for (int i = 1; i < N + 1; i++) {
            queue.offer(new Game(i, 1));
            int maxTurn = 0;

            while (!queue.isEmpty()) {
                Game game = queue.poll();

                for (int j = game.node; j < N + 1; j++) {
                    if (line[game.node][j]) {
                        queue.offer(new Game(j, game.turn + 1));
                    }
                }

                maxTurn = Math.max(maxTurn, game.turn);
            }

            bw.write(Integer.toString(maxTurn%2));
            bw.newLine();
        }

        bw.flush();
        bw.close();
    }
}

class Game {
    public int node;
    public int turn;

    public Game(int node, int turn) {
        this.node = node;
        this.turn = turn;
    }
}

공개 답안

import java.util.*;

class Main {
    static long n, a, b;
    static ArrayList<Long>[] v = new ArrayList[100050];
    static long[] dp = new long[100050];
    static final long inf = (long)1e12;

    static void dfs(long x, long par) {
        long ret = inf;
        for (Long nxt : v[(int)x]) {
            if (nxt == par) continue;
            dfs(nxt, x);
            ret = Math.min(ret, dp[nxt.intValue()]);
        }
        if (ret == inf) ret = 0;
        dp[(int)x] = x - ret;
    }

    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);  
        
        n=scanner.nextLong();
        
        for(int i=0;i<100050;i++)
            v[i]=new ArrayList<>();
            
        for(int i=1;i<n;i++){
            a=scanner.nextLong();
            b=scanner.nextLong();
            
            v[(int)a].add(b);
            v[(int)b].add(a);
        }
        
       dfs(1,0);
       
       for(int i=1;i<=n;i++){
           if(dp[i]>=0)
               System.out.println("1");
           else
               System.out.println("0");
       }
   } 
}