[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