[알고리즘] 백준 13023 - ABCDE

1. 문제

https://www.acmicpc.net/problem/13023
BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다. 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다.

오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다.

• A는 B와 친구다.
• B는 C와 친구다.
• C는 D와 친구다.
• D는 E와 친구다.

위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성하시오

2. 입력/출력

첫째 줄에 사람의 수 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을 출력한다.

3. 풀이

(참고 - https://andamiro25.tistory.com/79
https://www.acmicpc.net/board/view/38804
https://www.acmicpc.net/board/view/80580)

시간초과

• 1번

void DFS(int x, int depth, vector<vector<int>> list, vector<int> visit)

• 2번

void DFS(int x, int depth, vector<vector<int>> &list, vector<int> &visit) 

1번과 2번의 차이점
-> 1번의 경우 매개변수인 list와 visit이 그대로 전달되는 게 아니라, 같은 값을 가진 새로운 list와 visit로 복사되어 전달된다.
함수가 호출될 때 마다 N에 대해 복사가 일어나면서 오버헤드가 발생해 시간 초과가 된다.

복사를 낭비하는 시간을 줄이기 위해 &list와 같이 참조형으로 사용하면 값이 복사되는 대신 그대로 전달되며 시간 낭비가 되지 않는다.

4. 코드

using namespace std;

int n, m;
int answer = 0;

void DFS(int x, int depth, vector<vector<int>> &list, vector<int> &visit) {
    if (depth >= 4)
    {
        answer = 1;
        return;
    }

    for (int i = 0; i < list[x].size(); i++) {
        int next = list[x][i];
        if (visit[next] == 1) continue;
        visit[next] = 1;
        DFS(next, depth + 1,list, visit);
        visit[next] = 0;
    }
}


int main() 
{
    cin.tie(0);
    cout.tie(0);
    cin.sync_with_stdio(0);

    cin >> n >> m;

    vector<vector<int>> list(n);

    for (int i = 0; i < m; i++) {
        int x, y;

        cin >> x >> y;

        list[x].push_back(y);
        list[y].push_back(x);

    }



    for (int i = 0; i < n; i++) {
        vector<int> visit(n);
        visit[i] = 1;
        DFS(i, 0, list, visit);
        if (answer == 1) break;
    }

    cout << answer;
    return 0; 
}