[C/C++] 백준 : 13023번 : ABCDE

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

13023번: ABCDE

문제

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

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

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

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

입력

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

 

한 명을 통해 친구를 5명 확인할 수 있으면 친구 조건 A,B,C,D,E가 만족한다.

따라서, 위 문제에서 확인해야 하는 것은 1명을 통해 연속적으로 5명이 연결되어있는지 DFS를 통해 확인해야한다.

#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <string>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
#include <bitset>
#define INF 987654321
#define Mod 9901
#define CUNLINK ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
#define ll long long
#define ENDL cout << endl
#define endl '\n'

using namespace std;
typedef struct GraphNode {
	int cost;
	int dest;
	GraphNode* next;
}GraphNode;

typedef struct Graph {
	int cnt;
	GraphNode* adj;
}Graph;

bool visited[2001];
bool flag = false;

void Init_Graph(Graph* gph, int cnt) {
	gph->cnt = cnt;
	gph->adj = (GraphNode*)malloc(sizeof(GraphNode) * cnt);
	for (int i = 0; i < cnt; i++) gph->adj[i].next = NULL;
}

int AddDirectedLinkedEdge(Graph* gph, int src, int dst, int cost) {
	GraphNode* Temp = (GraphNode*)malloc(sizeof(GraphNode));
	Temp->cost = cost;
	Temp->dest = dst;
	Temp->next = gph->adj[src].next;
	gph->adj[src].next = Temp;
	return 1;
}

int AddUnDirectedLinkedEdge(Graph* gph, int src, int dst, int cost) {
	return AddDirectedLinkedEdge(gph, src, dst, cost) && AddDirectedLinkedEdge(gph, dst, src, cost);
}

void DFS(Graph* gph,int start, int depth) {
	if (depth == 4) {
		flag = true;
		return;
	}

	GraphNode* head = gph->adj[start].next;
	visited[start] = true;
	while (head) {
		if (!visited[head->dest]) {
			DFS(gph, head->dest, depth + 1);
			if (flag) return;
		}
		head = head->next;
	}
	visited[start] = false;
}

int main() {
	CUNLINK;
	Graph graph;
	int V, E;
	cin >> V >> E;
	Init_Graph(&graph, V);
	while (E--) {
		int a, b;
		cin >> a >> b;
		AddUnDirectedLinkedEdge(&graph, a, b, 1);
	}
	for (int i = 0; i < V; i++) {
		memset(visited, false, sizeof(visited));
		DFS(&graph, i, 0);
		if (flag) {
			cout << 1 << endl;
			return 0;
		}
	}
	cout << 0 << endl;
	
	return 0;
}