[백준 15900] 나무 탈출 (Java)

문제 링크: https://www.acmicpc.net/problem/15900

15900번: 나무 탈출

1. 주의할 점

- 트리 탐색시 방문 검사를 하지 않으면 TLE가 날 수 있다

 

2. 구현

- 간선에 대한 정보를 Li[] 배열에 담는다

- Root부터 idx Node까지의 거리를 Dist[idx]에 저장한다

- 트리 탐색을 하며, Leaf Node인 경우, Sum에 Dist[] 값을 추가한다

- 성원이가 게임을 이기기 위해서는 홀수번째 움직임에 게임이 끝나야 한다. 즉, Leaf Node부터 Root까지 거리의 합이 홀수여야 한다

 

[BFS]

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

class Main {
    static int node;
    static List<Integer> li[];
    static int dist[];      //root까지 거리
    
	public static void main (String[] args) throws java.lang.Exception {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    StringTokenizer st = new StringTokenizer(br.readLine());
	    node = Integer.parseInt(st.nextToken());
	    //초기화
	    dist = new int[node+1];
	    li = new List[node+1];
	    for(int i=1;i<=node;i++){
	        li[i] = new ArrayList<>();
	        dist[i] = -1;
	    }
	    
	    for(int i=0;i<node-1;i++){
	        String str = br.readLine();
	        st = new StringTokenizer(str);
	        int from = Integer.parseInt(st.nextToken());
	        int to = Integer.parseInt(st.nextToken());
	        li[from].add(to);
	        li[to].add(from);
	    }
	    Queue<Integer> q = new LinkedList<>();
	    q.offer(1);
	    dist[1]=0;
	    int sum=0;
	    while(!q.isEmpty()){
	        int idx = q.poll();
	        boolean isLeaf = true;
	        for(int i=0;i<li[idx].size();i++){
	            int next = li[idx].get(i);
	            if(dist[next]==-1){
	                isLeaf = false;
	                dist[next]=dist[idx]+1;
	                q.offer(next);
	            }
	        }
	        if(isLeaf)
	            sum+=dist[idx];
	    }
	    String answer = sum%2==0 ? "No" : "Yes";
		System.out.print(answer);
	}
}

 

[DFS]

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

class Main {
    static int node,sum;
    static List<Integer> li[];
    static int dist[];      //root까지 거리
    
    static void dfs(int idx){
        boolean isLeaf = true;
        for(int i=0;i<li[idx].size();i++){
            int next = li[idx].get(i);
	         if(dist[next]==-1){
	            isLeaf = false;
	            dist[next]=dist[idx]+1;
	            dfs(next);
	         }
	    }
	    if(isLeaf)
	        sum+=dist[idx];
    }
    
	public static void main (String[] args) throws java.lang.Exception {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    StringTokenizer st = new StringTokenizer(br.readLine());
	    node = Integer.parseInt(st.nextToken());
	    //초기화
	    sum=0;
	    dist = new int[node+1];
	    li = new List[node+1];
	    for(int i=1;i<=node;i++){
	        li[i] = new ArrayList<>();
	        dist[i] = -1;
	    }
	    
	    for(int i=0;i<node-1;i++){
	        String str = br.readLine();
	        st = new StringTokenizer(str);
	        int from = Integer.parseInt(st.nextToken());
	        int to = Integer.parseInt(st.nextToken());
	        li[from].add(to);
	        li[to].add(from);
	    }
	    dist[1]=0;
	    dfs(1);
	    String answer = sum%2==0 ? "No" : "Yes";
		System.out.print(answer);
	}
}