백준 13023(ABCDE)

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

13023번: ABCDE

해당 문제는 N명의 사람으로 구성 된 그룹이 있으며, 해당 그룹은 M개의 인원들이 친구 관계를 맺고 있다. 이때 아래와 같은 조건의 친구관계를 가지는 그룹일 경우 1 출력 아닐경우 0을 출력하는 문제이다.

 

주의 사항 :

N명의 사람이 최대 2000 명이기 때문에 2000번을 탐색하기에는 시간초과가 발생한다. 따라서 Vector 에 n 번째 인원의 친구 정보만 push 하는 과정을 통해 오직 친구인 사람의 번호만 Vector 에 저장하도록 한다. 

#include <iostream>
#include <vector>

using namespace std;

int n, m;
int flag = 0;
// map[n] 째 친구의 친구관계를 담을 Vector
vector<int> map[2001];

// 이미 한번 방문한 친구 번호 check
int used[2001];

void dfs(int start, int level){
	// 현재 이어진 친구 관계가 4개 라면 조건 부합
	if (level == 4){
		flag = 1;
		return;
	}

	for (int i = 0; i < map[start].size(); ++i){
		if (used[map[start][i]] == 1) continue;
		used[map[start][i]] = 1;
		dfs(map[start][i], level + 1);
		used[map[start][i]] = 0;
	}
}


int main(){
	//freopen_s(new FILE*, "tes.text", "r", stdin);
	cin >> n >> m;
	
    // 2000 by 2000 크기의 배열을 선언시 2000번의 연산을 한번의 재귀시 마다 수행해야 함으로
    // 비효율적 주어진 친구의 번호한 벡터에 추가시킨다.
	for (int i = 0; i < m; ++i){
		int y, x;
		cin >> y >> x;
		map[y].push_back(x);
		map[x].push_back(y);
	}

	// 0번 인원 부터 N번 째 인원까지의 친구관계를 확인
	for (int i = 0; i < n; ++i){
		used[i] = 1;
		dfs(i, 0);
		used[i] = 0;

		if (flag == 1) break;
	}

	if (flag == 1){
		cout << "1" << endl;
	}
	else{
		cout << "0" << endl;
	}

}