[백준] 15900번 나무 탈출 자바

문제

 

15900번: 나무 탈출

 

 

문제 풀이

 

ArrayList를 이용하여 트리를 만들고 dfs로 순회했다. 성원이가 이기려면 리프노드에서 루트노드까지 게임말을 옮길 때 홀수가 되어야 이길 수 있다. 하지만 짝수여도 다른 루트에서 또 짝수가 존재하면 그 루트의 말을 옮기면 되므로 이길 수 있다. 따라서 루트노드에서 리프노드까지의 각각의 루트 거리의 총합이 홀수이면 성원이는 이길 수 있다.

 

처음에 visited[]배열을 int형으로 받아서 방문표시와 해당 노드까지의 거리 합을 누적하면서 답을 구했다.

근데 계속 시간초과가 뜨길래, visited배열은 boolean형으로, dfs함수 내에서 누적합을 파라미터로 갱신해나갔는데 이것도 시간초과였다. 보니까 Scanner함수를 안쓰고 BufferedReader를 써야 시간초과가 나지 않았다...

 

 

소스 코드

 

public class b_15900 {

	static int N, total = 0;
	static ArrayList<Integer>[] list;
	static boolean[] visited;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		
		list = new ArrayList[N+1];
		for(int i = 1; i <= N; i++)
			list[i] = new ArrayList<Integer>();
		
		visited = new boolean[N+1];
		
		StringTokenizer st;
		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());

			list[a].add(b);
			list[b].add(a);
		}	
		
		visited[1] = true;
		dfs(1, 0);
		
		//짝수-짐, 홀수-이김
		String answer = (total % 2) == 0? "No" : "Yes";
		System.out.println(answer);
	}
	
	public static void dfs(int x, int sum) {
		
		for(int i = 0; i < list[x].size(); i++) {
			if(visited[list[x].get(i)] == false) {
				visited[list[x].get(i)] = true;
				dfs(list[x].get(i), sum+1);
			}
		}
		
		if(list[x].size() == 1)
			total += sum;
	}
    
   	/*
	public static void dfs(int x) {
		
		for(int i = 0; i < list[x].size(); i++) {
			if(visited[list[x].get(i)] == -1) {			//다음 노드가 방문되지 않았으면
				visited[list[x].get(i)] = visited[x] + 1;	//방문표시 후
				dfs(list[x].get(i));				//그 노드로 다시 dfs진행
			}
		}
		
		//인접 리스트 사이즈가 1이면 부모로 연결된 노드 하나이므로 리프노드다
		if(list[x].size() == 1)
			total += visited[x];
	}
	*/
		
}