BOJ 13023 ABCDE

문제

문제점

맞는 솔루션인것 같은데, 시간초과가 발생했다.
사이즈 계산해보니 탐색 중 시간초과가 나겠다고 예상했다.
원인은 원소 접근이었다. O(1)에 원소를 접근할 방법을 고민해보게 되었다.

해결 방법

vector<vector<int>> r(2001);

int main(){
    for (int i = 0; i < m; i++)
    {
        cin >> inp1 >> inp2;
        r[inp1].push_back(inp2);
        r[inp2].push_back(inp1);
    }
}

(코드의 많은 부분이 생략되었다)
아이디어는 무방향 간선에서 두개의 Edge에서 접근할 원소들을 미리 입력해주는 것이다.

코드

// 2021.10.14 22:17:22
// 13023 https://boj.kr/13023
#include <bits/stdc++.h>
using namespace std;

bool visited[2001];
vector<vector<int>> r(2001);
int n, m;

bool isFriendDepth(int cur, int depth)
{
    if (depth == 4)
        return true;

    visited[cur] = true;
    bool ret = false;
    //find cur.a -> someone
    for (int i = 0; i < r[cur].size(); i++)
    {
        int nextNode = r[cur][i];
        if (!visited[nextNode])
        {
            if (isFriendDepth(nextNode, depth + 1))
            {
                ret = true;
                break;
            }
        }
    }
    visited[cur] = false;
    return ret;
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    int inp1, inp2;
    cin >> n >> m;

    for (int i = 0; i < m; i++)
    {
        cin >> inp1 >> inp2;
        r[inp1].push_back(inp2);
        r[inp2].push_back(inp1);
    }

    for (int i = 0; i < n; i++)
    {
        if (isFriendDepth(i, 0) == true)
        {
            cout << 1;
            return 0;
        }
    }
    cout << 0;
    return 0;
}

한달이나 늦게 올린 이유

당시에는 언제든 다시 할 수 있는 생각이라고 생각했다.
오늘 다른 문제를 푸는데 같은 아이디어를 사용하게 되어서 생각나서 찾아 올렸다.