[DFS] 백준 13023번 ABCDE(C++)

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

 

 

코테 준비를 할때마다 느끼는 건데, 진짜 30분안에 안풀리면 무조건 답지를 보자.

오히려 내 방식대로 풀려다가 1시간 2시간 지나고 못풀면 그 자괴감이 더 크다.

 

심지어 푸는 방식도 달라서 내 접근법이 아예 틀렸을땐 정신적인 타격또한 후...

 

그나마 오늘푼건 1시간정도 끙끙대쓴데, 접근법은 맞아서 50%정도만 아팠다

 

내용은 간단하다

 

각 친구관계 사이가 주어졌을때 5명이 이어져서 친구인 관계가 존재하는가?

 

나는 여기서 

어라, 이거 dfs로 depth 가 4일때 끊으면 되는거 아닌가? 생각하고

그 각 값을 저장해줄 struct를 따로 만들어 보자고 생각했다

 

예를들어 struct s{

bool arr[2000]

}

 

을 하고, s를 배열로 정하는 거다

그래서 s[i].arr[j] 이렇게 정해서

 

arr이 true인 경우, 그 값으로 이어지는 거네?

 

그럼 타고타고 건너가서

 

depth가 4인경우가 존재하면 1 다 돌고 없으면 0으로하면되겟네

 

하고했는데

#include <iostream>

#include <string>

using namespace std;

bool visited[2000];

struct relation

{

    int arr[2000] = {0};

};

relation f[2000];

int n, m;

void task(int depth, int idx);

int main()

{

    cin >> n >> m;

    for (int i = 0; i < m; i++)

    {

        int x, y;

        cin >> x >> y;

        f[x].arr[y] = 1;

        f[y].arr[x] = 1;

    }

    for (int i = 0; i < n; i++)

    {

        task(0, 0);

    }

    cout << 0 << "\n";

}

void task(int depth, int idx)

{

    if (depth == 4)

    {

        cout << 1 << "\n";

        exit(0);

    }

    for (int j = 0; j < n; j++)

    {

        if (f[idx].arr[j] == 1 && !visited[idx])

        {

            visited[idx] = true;

            task(depth + 1, j);

            visited[idx] = false;

        }

    }

}

그래.. 어찌 세상이 그리 쉽겠는가

 

 

대충 풀이 접근 자체는 맞는거 같은데 시간초과가 너무 많이 났다..

나 죽는줄

 

 

시간초과가 나는 이유를 계속 고민해봤는데

아무리봐도 모든 노드를 확인하는 저 두번째 for문이 문제인 것 같았다

 for (int j = 0; j < n; j++)

    {

        if (f[idx].arr[j] == 1 && !visited[idx])

        {

            visited[idx] = true;

            task(depth + 1, j);

            visited[idx] = false;

        }

    }
요놈;;

 

그래서 인터넷 검색을 한 결과, fifo인 vector를 사용하면 저렇게 모든 노드를 돌지 않고, 각 인덱스에 접근할 수 있겠더라

 

난 왜 저 생각을 못했나

 

#include <iostream>

#include <string>

#include <vector>

using namespace std;

bool visited[2000];

vector<int> f[2000];

int n, m;

void task(int depth, int idx);

int main()

{

    cin >> n >> m;

    if (m < 4)

    {

        cout << 0 << "\n";

        exit(0);

    }

    for (int i = 0; i < m; i++)

    {

        int x, y;

        cin >> x >> y;

        f[x].push_back(y);

        f[y].push_back(x);

    }

    for (int i = 0; i < n; i++)

        task(0, i);

    cout << 0 << "\n";

}

void task(int depth, int idx)

{

    if (depth == 4)

    {

        cout << 1 << "\n";

        exit(0);

    }

    visited[idx] = true;

    for (int j = 0; j < f[idx].size(); j++)

    {

        if (!visited[f[idx][j]])

        {

            task(depth + 1, f[idx][j]);

        }

    }

    visited[idx] = false;

}

 

vector 가 참 좋은듯