[Java] 백준 - 3584번: 가장 가까운 공통 조상

9월 14일(목) - 트리 (3584번)

3584번: 가장 가까운 공통 조상

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이

(C언어 풀이 활용)

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

import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());

        while (T > 0)
        {
            T--;

            int N = Integer.parseInt(br.readLine());
            int[] parent = new int[N+2];
            boolean[] visited = new boolean[N+2];

            for(int i=1; i<=N; i++)
            {
                visited[i] = false;
                parent[i] = i;
            }

            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());
                parent[B] = A;
            }

            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            visited[u] = true;

            while (u != parent[u])
            {
                u = parent[u];
                visited[u] = true;
            }

            while (true)
            {
                if(visited[v] == true || v == parent[v])
                {
                    break;
                }
                else
                {
                    v = parent[v];
                }
            }

            System.out.println(v);
        }

    }
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ