SW Expert Academy 의 1219번 - 길찾기 문제입니다.
방향이 있는 그래프에서 0번에서 99번까지 가는 길이 존재하는지 살펴보는 문제입니다.
처음 문제만 보았을 때는 DFS로 풀어야 할 지, 아니면 더욱 심화된 것인지 헷갈렸는데
자세히 살펴보니 순서쌍만 제대로 따라가면서 끝에 99가 나오는지 살펴보기만 하면 되었습니다.
- 난이도 : 2~3
문제 조건
- 총 10개의 테스트 케이스가 주어진다.
- 각 정점에서 나아갈 수 있는 길은 최대 2갈래 뿐이다.
- 진행방향은 화살표 방향을 거스를 수 없다.
- 가령, (0, 1), (0, 2) 가 인풋에 주어졌다면 0번에서 1번, 0번에서 2번 방향으로만 갈 수 있다.
- 인풋으로 주어지는 정점의 총 갯수는 출발점과 도착점을 제외하고 98개를 넘지 않는다.
Input
첫 줄에는 테스트 케이스 번호, 그 다음 줄에는 순서쌍이 주어진다.
Output
끝까지 가는 길이 존재하면 1, 아니면 0을 출력한다.
처음에 생각한 아이디어
(0, 1) (0, 2) (1, 4) (1, 3), … 과 같이 인풋이 주어지므로, 2차원 벡터를 생각했습니다.
즉, 0번 벡터의 1번째 인덱스에 1이, 2번째 인덱스에 2가 들어가는 형태입니다. 그림으로 나타내면 다음과 같습니다.
최대 2개까지로 길이 제한되어 있으므로, 각 정점 당 인덱스가 2개만 필요합니다.
또한 길이 두 가지 존재하는 정점에 갔을 경우, 갈 수 있는 길을 스택에 쌓을 수 있도록 스택도 사용했습니다.
즉, 기본적인 길은 벡터 자료구조에 담아 두고, 길의 탐색은 스택을 활용하기로 했습니다.
전체적인 길의 구조가 두 갈래의 한 가지 방향성을 가지고 있기 때문에 기존의 DFS 방식에서 사용하던 그래프와는 조금 달랐고, 따라서 DFS의 visited 배열 및 기존의 탐색 방법과는 조금 다르게 구현해 보았습니다.
0번에서 갈 수 있는 정점은 1과 2 이므로 스택에 쌓고,
top인 2를 pop한 후, 2에서 갈 수 있는 정점을 스택에 쌓고, …,
이 과정을 top에 99가 있을 때까지 반복합니다.
소스코드
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 <stack>
#include <vector>
#include <fstream>
using namespace std;
stack<int> s;
int ans;
int main(void) {
int test_case, n, idx, val;
int j, result = 0;
for(int T=0; T<10; T++){
cin >> test_case;
cin >> n;
vector<vector<int>> v(n);
for (int i = 0; i < n; i++) {
cin >> idx; cin >> val;
v[idx].push_back(val);
}
// 0번 인덱스부터 차례로 확인한다.
j = 0;
do{
for(int k = 0; k<v[j].size(); k++)
s.push(v[j][k]);
j = s.top();
if (j == 99){
result = 1;
break;
}
s.pop();
} while (!s.empty());
cout << "#" << test_case << " " << result << endl;
if (!s.empty()) {
while (!s.empty())
s.pop();
}
v.clear();
result = 0;
}
return 0;
}
c++의 STL에서 제공하는 stack 자료구조와 vector를 사용하였습니다.