[백준/C++] 13023 - ABCDE

풀이 시간: 35m34s75(초기 코드) + 14m(시간 초과 수정)

시간 복잡도: O(N*M^4)

공간 복잡도: O(N+M)

문제

BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다. 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다.
오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다.
- A는 B와 친구다.
- B는 C와 친구다.
- C는 D와 친구다.
- D는 E와 친구다.
위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 사람의 수 N (5 ≤ N ≤ 2000)과 친구 관계의 수 M (1 ≤ M ≤ 2000)이 주어진다.
둘째 줄부터 M개의 줄에는 정수 a와 b가 주어지며, a와 b가 친구라는 뜻이다. (0 ≤ a, b ≤ N-1, a ≠ b) 같은 친구 관계가 두 번 이상 주어지는 경우는 없다.

출력

문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다.

문제 풀이

초기 코드는 다음과 같았다. 본 코드에서는 시간초과가 발생했는데, 원인을 찾기 어려워 다른 코드를 참고해서 내 코드의 문제점을 확인해보았다.

초기 코드

#include <iostream>
#include <vector>
using namespace std;
int N, M, a, b;
bool ans = false;
vector<vector<bool>> arr;
vector<bool> visited;

void dfs(int n, int cnt) {
    if (cnt == 4) { ans = true; return; }
    visited[n] = true;
    for (int i = 0; i < N; ++i)
        if (!visited[i] && arr[n][i]) dfs(i, cnt + 1);
    visited[n] = false;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> N >> M;
    arr = vector<vector<bool>>(N, vector<bool>(N, false));
    visited = vector<bool>(N, false);
    for (int i = 0; i < M; ++i) {
        cin >> a >> b;
        arr[a][b] = arr[b][a] = true;
    }
    for (int i = 0; i < N; ++i) {
        dfs(i, 0);
        if (ans) break;
    }
    cout << ans;
    return 0;
}

 

위 코드의 문제는 "인접 행렬"때문이었다.

vector<vector<bool>> arr를 사용하여 모든 노드를 표현하고 각 노드 사이의 연결 여부를 bool 형태로 저장했다.

이 경우에는 모든 노드를 탐색하며 각 노드에 대해 모든 다른 노드를 확인해야 한다. 따라서 불필요한 노드까지 방문하게 되고, 이는 시간 초과로 이어진다.

 

반면 다른 블로그의 코드에서는 "인접 리스트"로 노드들의 연결 상태를 관리하고 있었다.

참고한 블로그는 다음과 같다.

https://primayy.tistory.com/29

이와 같이 인접 리스트 형태로 vector<int> arr[2000] 또는 vector<vector<int>> arr 로 하게 되면, 일단 N개의 노드에 대한 벡터를 저장하고, 각 노드에서 친구 관계인 노드들만 연결을 하도록 하는 것이다.

따라서 여기서 저장값은 인접 행렬의 bool 형태와는 달리, int 형으로 연결된 노드들, 즉 친구들을 리스트로 저장해두는 것이다. 이 경우에는 친구 관계에 있는 노드들만 리스트에서 찾아 방문하기 때문에 불필요한 노드를 방문하지 않는다.

 

따라서, 인접 리스트로 변경하면 O(N^2)에서 O(N)으로 공간복잡도를 줄일 수 있다. 본인도 인접 리스트를 사용하여 코드를 수정해보았다.

전체 코드

#include <iostream>
#include <vector>
using namespace std;
int N, M, a, b;
bool ans = false;
vector<vector<int>> arr; // 인접 리스트로 변경
vector<bool> visited;

void dfs(int n, int cnt) {
    if (cnt == 4) { ans = true; return; } // 4개일 경우 true
    visited[n] = true;
    for (int i = 0; i < arr[n].size(); ++i) // 해당 노드의 친구들만 순회
        if (!visited[arr[n][i]]) dfs(arr[n][i], cnt + 1); // 방문하지 않은 경우 방문
    visited[n] = false; // 백트래킹
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> N >> M;
    arr = vector<vector<int>>(N); // 첫 번째 차원만 N으로 초기화
    visited = vector<bool>(N, false);
    for (int i = 0; i < M; ++i) {
        cin >> a >> b;
        arr[a].push_back(b); // 인접 리스트로 변경
        arr[b].push_back(a);
    }
    for (int i = 0; i < N; ++i) {
        dfs(i, 0);
        if (ans) break;
    }
    cout << ans;
    return 0;
}

 

https://www.acmicpc.net/problem/13023