[BOJ_20364] 부동산 다툼

설명

---

반대로 내가 찾아야 하는 곳에서 트리를 올라간다고 생각하고 방문 여부를 차차 검색하면 쉽게 풀 수 있는 문제였다. 처음에 트리를 구현해서 탐색하는 생각으로 접근 했다가는 뭔가 이상한듯 하여서 다른 풀이들을 참고 하였는데 굉장히 쉬운 방법이 이렇게 있었다.

 

코드

---

package tree;

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

public class BOJ_20364 {
    public static void main(String[] args) throws Exception{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tk = new StringTokenizer(in.readLine()," ");
        int N = Integer.parseInt(tk.nextToken()); 
        int Q = Integer.parseInt(tk.nextToken()); 

        int[] duck = new int[Q];
        for (int i = 0; i < Q; i++) {
            tk = new StringTokenizer(in.readLine()," ");
            duck[i] = Integer.parseInt(tk.nextToken());
        }
        solution(duck, N);
    }

    private static void solution(int[] duck,int N) {
        boolean[] visited = new boolean[N + 1];

        for (int x : duck){
            int ans = 0;
            int tmp = x;
            while (x != 1){
                if(visited[x]) ans = x;
                x /= 2; //이진 트리
            }
            visited[tmp] = true;
            System.out.println(ans);
        }
    }

}

 

20364번: 부동산 다툼