[백준] 20364 부동산 다툼 - 트리(Tree) + 트리의 성질 JAVA

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

20364번: 부동산 다툼

코드설명

트리의 원리를 활용하여 트리없이 해결할 수 있습니다.

 

처음에 문제를 보고, addNode라는 트리의 구조를 만들어 진행하려고했지만, 

1

2 3

4 5 6

이런식으로 되어있는 트리의 모양을 만들다가 실패했습니다.

 

트리의 구조를 만들지 않고, 트리의 끝에서부터 올라오며 마지막에 만난 트리의 이미 방문한 점이 있다면, 해당 방문점을 기준으로 더 이상 접속하지 못하니 해당 점을 출력하면 다른 오리가 이미 점유한 땅이 될 것 입니다.

 

아래 코드에서 보이듯 방문한 상태라면 해당 방문한 곳을 visited 처리해주어야합니다.

if(flag == true) { //불가능한 상태.
    System.out.println(firstMeetPosition);
}else if(flag == false) { //방문한 상태
    visited[a] = true;
    System.out.println("0");
}

코드

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

public class Main {
	public static int N, Q;
	public static int[] arr;
	public static boolean[] visited;
	public static int answer = 0;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine()); 	
    	
    	N = Integer.parseInt(st.nextToken());
    	Q = Integer.parseInt(st.nextToken());
    	visited = new boolean[N+1];
    	
    	for(int i=0;i<Q;i++) {
    		st = new StringTokenizer(br.readLine());
    		int a = Integer.parseInt(st.nextToken());
    		boolean flag = false;
    		int firstMeetPosition = 1;
    		for(int j=a; j>=2; j/=2) {
    			if(visited[j] == true) {
    				flag = true;
    				firstMeetPosition = j;
    			}
    		}
    		
    		if(flag == true) { //불가능한 상태.
    			System.out.println(firstMeetPosition);
    		}else if(flag == false) {
    			visited[a] = true;
    			System.out.println("0");
    		}
    		
    	}
    } 
}