백준 13023 c++ "ABCDE" -PlusUltraCode-

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

 

 

[필자 사고]

친구관계 ABCDE 를 구하는 문제이다.

DFS를 이용하여 depth 가 5이상인 경우를 구하면 문제를 풀 수 있따.

 

이 문제의 key point 는 방문한 visted를 false 처리를 마지막에 해줘서 

depth가 5이상 만들어질 수 있는 경우임에도 불구하고 못 만들어지는 상황을 미연에 방지할 수 있게 된다.

 

[소스 코드]

 

#include <iostream>
#include <vector>

using namespace std;

int N, M;
vector<vector<int>> arr;
int resultFlag = 0;

void Input() {
	cin >> N >> M;
	arr.resize(N + 1);
	for (int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;
		arr[a].push_back(b);
		arr[b].push_back(a);
	}
}

void DFS(int startNum, int depth,vector<bool> &visited) {
	if (visited[startNum] == true|| resultFlag == 1)return;
	visited[startNum] = true;
	if (depth >= 5) {
		resultFlag = 1;
		return;
	}

	for (int nextNum : arr[startNum]) {
		if (visited[nextNum] == false) {
			
			DFS(nextNum, depth + 1, visited);
		}
	}

	visited[startNum] = false;
}

void GameStart() {
	for (int i = 0; i <= N; i++) {
		vector<bool> visited(N, false);
		DFS(i, 1, visited);
		if (resultFlag == 1)return;
	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	Input();
	GameStart();
	cout << resultFlag;
}