1. ๋ฌธ์ ์ ๋ํ์ฌ ๐ฆ
- ๋ฌธ์ ๋งํฌ: https://www.acmicpc.net/problem/22856
(1) ์กฐ๊ฑด ๋ถ์ ๐
- ์ค์ ์ํ๋ก ๋์ค๋ ๋ง์ง๋ง ๋ ธ๋๋ฅผ, ๋ฌธ์ ์์ ์ฃผ์ด์ง ์กฐ๊ฑด์ธ '์ ์ฌ ์ค์ ์ํ' ๋ฐฉ์์ผ๋ก ๋ ธ๋๋ฅผ ์ํ ํ์ ๋, ๋ช ๋ฒ์ ์ด๋๋ง์ ์ค์ ์ํ ์ ๋ง์ง๋ง ๋ ธ๋์ ๋๋ฌํ ์ ์๋์ง ์ด๋ ํ์๋ฅผ ๊ตฌํด๋ผ
- ์ฌ๊ธฐ์
์ด๋์ด๋ ํ๋์ใ ข ๋ ธ๋์์ ๋ค๋ฅธ ๋ ธ๋๋ก ํ ๋ฒ ์์ง์ด๋ ํ์์ด๋ค.
2. ์ฝ๋๊ฐ ๋์ค๊ธฐ๊น์ง ๐ ๏ธ
KEY WORD: DFS
- ์ค์ ์ํ ๋ง์ง๋ง ๋ ธ๋ ๊ตฌํ๊ธฐ
- ์ ์ฌ ์ค์ ์ํ ๊ตฌํํด์ ๋ง์ง๋ง ๋ ธ๋๊น์ง์ ๋ฐฉ๋ฌธ ํ์ ๊ตฌํ๊ธฐ
(1) ์๊ฐ๋ณต์ก๋ ๋ถ์ โณ
์ต๋ ๋ ธ๋ ๊ฐ์๊ฐ $100,000$ ๊ฐ ์ธ๋ฐ, DFS๋ $O(V + E)$ ์์ผ๋ก, $200,000$ ๊ฐ๋ฅผ ์ ๋๋๋ค.
3. ์ฝ๋ ๐
import java.io.*;
import java.util.*;
public class Main {
static int N, last_one, cnt;
static int answer = 0;
static ArrayList<Integer> [] lists;
static boolean [] check;
public static void main(String[] args) throws IOException {
init();
inorder_traversal(1);
similar_inorder(1);
System.out.printf("%d", answer);
}
public static void inorder_traversal(int now) {
if(lists[now].get(0) != -1) inorder_traversal(lists[now].get(0));
last_one = now;
if(lists[now].get(1) != -1) inorder_traversal(lists[now].get(1));
}
public static void similar_inorder(int now) {
if(lists[now].get(0) != -1 && !check[lists[now].get(0)]) {
cnt++;
similar_inorder(lists[now].get(0));
cnt++;
}
if(lists[now].get(1) != -1 && !check[lists[now].get(1)]) {
cnt++;
similar_inorder(lists[now].get(1));
cnt++;
}
if(now == last_one) {
answer = cnt;
return;
} else check[now] = true;
}
public static void init() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
lists = new ArrayList[N+1];
check = new boolean[N+1];
for(int i = 1; i <= N; i++){
lists[i] = new ArrayList<>();
}
for(int i = 0; i < N; i++){
StringTokenizer st = new StringTokenizer(br.readLine());
int me = Integer.parseInt(st.nextToken());
int left = Integer.parseInt(st.nextToken());
int right = Integer.parseInt(st.nextToken());
lists[me].add(left);
lists[me].add(right);
}
}}
4. ํธ๋ฌ๋ธ ์ํ or ๋ฐฐ์ด ์ ๐
๋ค๋ฅธ ์ฌ๋์ ํ์ด๋ฅผ ๋ณด๋, ์ํ์ ์ฌ๊ณ ๋ฅผ ํด์ ํ๋ฉด, ์๊ฐ์ ๋ ๋จ์ถํ ์ ์์๋ค.
์ค์ ์ํ๋ ์ธ์ ๋ ์ค๋ฅธ์ชฝ ์ ์ผ ๋์ ์๋ ๋
ธ๋๋ฅผ ๊ณ ๋ฅธ๋ค.

์จ์ ํ DFS๋ฅผ ๊ฑฐ์น๋ค๊ณ ์น๋ฉด์ ์ด๋ ํ์ = ๊ฐ์ ์ ๊ฐ์ x 2* ์ด๋ค.

์ฌ๊ธฐ์ ๋งจ ๋ง์ง ๋
ธ๋์ ๊น์ด๋งํผ ๋นผ์ฃผ๊ธฐ๋ง ํ๋ฉด ๋ต์ด ๋๋ค.
์ฆ ๊ฐ์ ์ ๊ฐ์ x 2 - ๋ฃจํธ ๋ ธ๋๋ถํฐ ์ค์ ์ํ ๋ง์ง๋ง ์กฐํ ๋ ธ๋๊น์ง์ ๊น์ด
import java.io.*;
import java.util.*;
public class Main {
static int N;
static ArrayList<Integer>[] lists;
static int lastNode; // ์ค์์ํ ๋ง์ง๋ง ๋
ธ๋ ๋ฒํธ
static int lastDepth; // ๋ง์ง๋ง ๋
ธ๋๊น์ง์ depth
public static void main(String[] args) throws IOException {
init();
findLastNode(1); // 1. ์ค์์ํ๋ก ๋ง์ง๋ง ๋
ธ๋ ์ฐพ๊ธฐ
findDepth(1, 0); // 2. ๋ง์ง๋ง ๋
ธ๋๊น์ง์ depth ํ์
int edgeCount = N - 1; // 3. ์ ์ฒด ๊ฐ์ ๊ฐ์
int answer = edgeCount * 2 - lastDepth;
System.out.println(answer);
}
// ์ค์์ํ๋ก ๋ง์ง๋ง ๋
ธ๋ ๋ฐ๊ฒฌ
static void findLastNode(int now) {
if (lists[now].get(0) != -1) findLastNode(lists[now].get(0));
lastNode = now;
if (lists[now].get(1) != -1) findLastNode(lists[now].get(1));
}
// DFS๋ก lastNode๊น์ง์ ๊ฑฐ๋ฆฌ(depth) ์ธก์
static void findDepth(int now, int depth) {
if (now == -1) return;
if (now == lastNode) lastDepth = depth;
if (lists[now].get(0) != -1) findDepth(lists[now].get(0), depth + 1);
if (lists[now].get(1) != -1) findDepth(lists[now].get(1), depth + 1);
}
public static void init() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
lists = new ArrayList[N+1];
for(int i = 1; i <= N; i++)
lists[i] = new ArrayList<>();
for(int i = 0; i < N; i++){
StringTokenizer st = new StringTokenizer(br.readLine());
int me = Integer.parseInt(st.nextToken());
int left = Integer.parseInt(st.nextToken());
int right = Integer.parseInt(st.nextToken());
lists[me].add(left);
lists[me].add(right);
}
}
}
0