어흥
[백준 15900] 나무 탈출 (Java) 본문
728x90
반응형
문제 링크: https://www.acmicpc.net/problem/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);
}
}
728x90
반응형
'알고리즘 > 백준' 카테고리의 다른 글
[백준 9470] Strahler 순서 (Java) (0) | 2021.10.07 |
---|---|
[백준 14676] 영우는 사기꾼? (0) | 2021.10.07 |
[백준 22867] 종점 (C++) (0) | 2021.10.02 |
[백준 17612] 쇼핑몰 (C++) (0) | 2021.10.02 |
[백준 20040] 사이클 게임 (C++) (0) | 2021.08.30 |
Comments