[BOJ] - 13023. ABCDE

[URL]

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

13023번: ABCDE

 

[풀이 과정]

*그래프 구현(벡터), 깊이우선탐색(DFS)

 

1. 배열로 깊이 우선 탐색 (시간 초과)

2. 그래프 깊이 우선 탐색

3. 연결관계 4개 찾으면 flag = 1로 바꿔주고 

flag 값 검색하여 1이면 return;

 

[소스 코드]

 

#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;
#define MAX 2005
 
int N, M;
vector <int> graph[MAX];
bool check[MAX];
bool flag = 0;
 
void DFS(int cur, int cnt) {
    if (cnt == 4)
    {
        flag = 1;
        return;
    }
 
    check[cur] = true;
 
    for (int i = 0; i < graph[cur].size(); i++)
    {
        int next = graph[cur][i];
 
        if (check[next] == false)
        {
            DFS(next, cnt + 1);
        }
        if (flag == 1)
        {
            return;
        }
    }
 
    check[cur] = false;
}
 
int main() {
    scanf("%d %d", &N, &M);
    for (int i = 0; i < M; i++)
    {
        int a, b;
        scanf("%d %d", &a, &b);
 
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
 
    for (int i = 0; i < N; i++)
    {
        memset(check, 0, sizeof(check));
 
        if (flag == 1)
            break;
 
        DFS(i, 0);
    }
 
    printf("%d\n", flag);
 
    return 0;
}