[C++ / 백준 13023번] ABCDE

문제

 

 

 

시행 착오

 

 그래프가 기억이 안 나서 복습했다.

백트래킹, dfs 는 잘 하지만 그래프와 합쳐지니 연상이 잘 안 되었다. 항상 천천히 알고리즘을 생각해내는 연습이 필요해 보인다. (무작정 아는 방식으로 구현 X 머릿속에서 구체화)

 

해결 방법

 

그래프를 선언하고, 각 그래프마다 관계 또한 최대 2000개까지 들어올 수 있다.

사실상 2차원 배열 형태를 벡터를 이용해 표현한 것과 비슷한데, 

 

1. 시작 노드를 정한다.
2. 시작 노드에 저장되어있는 관계로 접근한다.
3. 노드의 관계를 깊이우선탐색 하면서 cnt 가 4가 되는 노드순서를 찾는다.
4. 끝

 

 

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;


int N, M;
vector<int> g[2000];

bool visited[2000] = { false };

bool exist = false;

void dfs(int node, int cnt)
{
    if (cnt == 4)
    {
        
        exist = true;
        return;

    }

    for (int i = 0; i < g[node].size(); i++)
    {
        int nextnode = g[node][i];

        if (!visited[nextnode])
        {
            visited[nextnode] = true;

            dfs(nextnode, cnt+1);

            visited[nextnode] = false;
        }
     
    }

}

int main()
{
  
    cin >> N >> M;

    for (int i = 0; i < M; i++)
    {
        int u, v;
        cin >> u >> v;

        g[u].push_back(v);
        g[v].push_back(u);

    }


    for (int i = 0; i < N; i++)
    {
        if (!visited[i])
        {
            visited[i] = true;
            dfs(i, 0);
            visited[i] = false;
        }

        if (exist)
        {
            cout << "1";
            return 0;
        }
    }

        if(!exist) cout << "0";

    return 0;
}