https://www.acmicpc.net/problem/30893
처음 이문제에 접근했을때 문제를 이해하는데 진짜 오래걸렸던 기억이 있어서 다시 풀어봤습니다.
다행히도 백준에 실려있는 문제는 설명이 잘되어있어서 이해하기가 수월하더라고요! 물론 두번째 보는거라 그런거긴 한데
그래도 확실히 게임이론은 어려운것 같습니다..
이 문제는 S에서 출발하여 말을 한번씩 번갈아가면서 옮길 수 있고, E에 먼저 도착하는 사람이 이기는 게임으로 선공을 할지, 후공을 할지 구하는 문제입니다.
dfs를 통해서 문제를 접근했고, E에 도착하면 true를 리턴해줍니다.
그다음 자식 노드들 중에서 true인 경우가 하나라도 있으면 true를 리턴해주시면 됩니다
"더는 말을 움직일 수 없게 되면 게임이 종료됩니다."
라는 말이 문제에 명시되어 있어서 상대가 자식노드가 없는 정점으로 보내버린다면 게임을 지게됩니다.
이 예외까지 생각하여 true를 최종으로 리턴받는다면 선공을, 아니면 후공을 선택하도록 합니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
#include <iostream>
#include <vector>
#define MAX 100001
using namespace std;
vector<int> graph[MAX];
bool visit[MAX];
int N, S, E, ret;
bool dfs(int v, int t) {
if (v == E) return true;
visit[v] = true;
int cnt = 0;
bool flag = false;
for (auto next : graph[v]) {
if (visit[next]) continue;
flag |= dfs(next, 1 - t);
cnt++;
}
if (t && cnt > 1) return false;
return flag;
}
void func() {
if (dfs(S, 0)) cout << "First\n";
else cout << "Second\n";
}
void input() {
int u, v;
cin >> N >> S >> E;
for (int i = 1; i < N; i++) {
cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
}
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
func();
return 0;
}
|
cs |
'algorithm > dfs' 카테고리의 다른 글
| boj 19542 전단지 돌리기 (0) | 2024.06.19 |
|---|---|
| boj 19236 청소년 상어 (0) | 2021.04.22 |
| boj 2239 스도쿠 (0) | 2021.04.16 |
| boj 2458 키 순서 (0) | 2021.04.13 |
| boj 14889 스타트와 링크 (0) | 2021.03.17 |