[백준] 15900 - 나무 탈출

[백준] 15900 - 나무 탈출

[문제링크]

0. 모든 leaf 노드에 말이 있으며, 한 번에 하나씩 부모로 올리는 게임

모든 leaf 노드의 차수의 합에 따라 승/패를 알 수 있다 (짝수면 선공 패배, 홀수면 선공 승리)

1. 시작 노드는 1번으로 고정이므로, BFS를 이용해 모든 노드를 탐색, leaf 여부 및 depth를 저장한다

2. BFS를 진행할 때

연결된 노드에 이미 depth 정보가 있다면 : 이미 방문한 노드, 즉 부모 노드이다

depth 정보가 없다면 : 방문하지 않은 노드, 자식 노드이므로 현재 depth +1을 해당 노드의 depth로 저장한다

3. 탐색이 종료된 후 leaf로 마킹된 노드들을 찾아 depth를 전부 합산, 2의 배수인지에 따라 정답을 출력한다

※ BFS가 아닌 DFS로 진행했다면, leaf 노드 여부/깊이를 따로 저장하지 않고 즉시 판단, 처리 가능하므로 더 편했을것 같다

import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class Main{ public static void main(String[] args)throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = pint(br.readLine()); int[] depth = new int[N]; boolean[] isLeaf = new boolean[N]; ArrayList> graph = new ArrayList<>(); for (int i = 0; i < N; i++) { graph.add(new LinkedList<>()); depth[i]=-1; } for (int i = 0; i < N-1; i++) { StringTokenizer st = new StringTokenizer(br.readLine()); int a=pint(st.nextToken())-1; int b=pint(st.nextToken())-1; graph.get(a).add(b); graph.get(b).add(a); } Queue qu = new LinkedList<>(); int curNode=0; int curDepth=0; depth[curNode]=curDepth; qu.offer(curNode); isLeaf[curNode]=true; while(!qu.isEmpty()) { curNode=qu.poll(); for(int nextNode : graph.get(curNode)) { if(depth[nextNode]!=-1)continue; depth[nextNode]=depth[curNode]+1; isLeaf[nextNode]=true; isLeaf[curNode]=false; qu.offer(nextNode); } } int ans=0; for(int i=0; i

결과 화면

from http://nato-blog.tistory.com/165 by ccl(S) rewrite - 2021-12-25 16:26:55