[C++] 13023 ABCDE
👉 13023 ABCDE
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int dfs(int start, vector<vector<int>> &graph, vector<int> &visited);
int main(){
int n, m;
int f1, f2;
int i, j;
int flag = 0;
vector<vector<int>> graph;
vector<int> visited;
cin >> n >> m;
for (i = 0; i < n; i++) {
vector<int> v;
graph.push_back(v);
visited.push_back(0);
}
for (i = 0; i < m; i ++) {
cin >> f1 >> f2;
graph[f1].push_back(f2);
graph[f2].push_back(f1);
}
for (i = 0; i < n; i++) {
visited[i] = 1;
if (dfs(i, graph, visited) >= 4) {
flag = 1;
break;
}
visited[i] = 0;
}
cout << flag << endl;
return 0;
}
int dfs(int start, vector<vector<int>> &graph, vector<int> &visited) {
if (graph[start].size() != 0) {
int res = 0;
for (int i = 0; i < graph[start].size(); i++) {
int node = graph[start][i];
if (visited[node] == 0) {
visited[node] = 1;
res = max(dfs(node, graph, visited) + 1, res);
if (res >= 4) {
return res;
}
visited[node] = 0;
}
}
return res;
}
return 0;
}
[풀이]
dfs로 탐색하면서 4번 이상 탐색이 진행되면(깊이가 4 이상이면) 조건에 성립하는 것으로 간주하였다.
(체크) dfs()
'깊이'에 대한 변수를 설정하여 한 단계를 내려갈 때마다 +1 해주면 어떨까? 라는 생각을 했지만, dfs는 재귀로 진행되기 때문에 변수 하나로 관리할 수 없다. (예를 들어, a - [b, c, d] 일 경우 b 노드에 대한 dfs, c 노드에 대한 dfs, d 노드에 대한 dfs 모두 진행되기 때문이다.)
- '재귀' -> 거꾸로 생각해보자
- a - b - c - d - e 의 dfs(재귀)가 진행된다면 a에서의 dfs는 b - c - d - e의 결과를 반영한다. b 에서의 dfs는 c - d -e 의 결과를 반영한다.
- 끝 노드에 도착했을 때 0을 반환하고, 그 외의 경우에는 뒤로 연결된 노드에 대한 dfs() 값 + 1을 반환하도록 한다. (e에서는 0을 반환, d에서는 e에 대한 dfs() + 1, c에서는 d에 대한 dfs() + 1 ...)
- 모든 길 중 가장 먼 거리를 반영하기 위해 max()로 최댓값을 갱신한다.
(체크) visited[node] = 1;
-> dfs()
-> visited[node] = 0;
한 노드에 연결되어 있는 모든 노드를 for()문으로 접근하여 각각 dfs()를 진행하기 때문에, 한노드에 대한 dfs()를 진행한 뒤 방문여부를 초기화시켜주어야 한다.
vector
- C++ STL에 있는 컨테이너로 가변적으로 크기가 변하는 배열로 생각할 수 있다.
- 생성 시 힙 메모리에 생성되며 동적할당된다.
- 속도는 배열에 비해 느리지만 메모리를 효율적으로 관리할 수 있다.
vector 참조 1
vector 참조 2
[시간 초과]
처음엔 모든 노드를 출발점으로 하여 최대 깊이를 다 구한 후 4 이상인 곳이 있다면 정답 처리가 되도록 구현하였다. 그러나, 문제의 조건 상 5 <= N < 2000이기 때문에 모든 경우를 구하기엔 시간이 부족하다. 깊이가 4 이상인 곳이 발견된다면 탐색을 멈추고 바로 정답 처리하도록 코드를 수정하자. if (res >= 4) return res
[적용 자료구조 및 알고리즘]
- vector
- DFS
Author And Source
이 문제에 관하여([C++] 13023 ABCDE), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@yuchan/C-13023-ABCDE저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)