ABCDE - 13023 - 백준 - C++

ABCDE 문제 바로가기
해당 문제는 BackTraking을 사용하는 문제입니다.
문제 자체는 어렵지 않은데, 문제가 뭔 말을 하는지 이해가 되지 않아서, 다른 블로그에서 해설 조금 + 반례를 참고하여 풀었습니다.

일단 이 문제가 요구하는 것은 0 1 2 3 4 5 6 7 8 9 10... 이렇게 2000명이 있는데, 1 -> 3 -> 4 -> 2 -> 199 이런 하나의 노드에서 DFS를 했을때 Depth가 5개가 되는 경우가 하나라도 있는지를 물어보는 것입니다.

코드로 확인해 보면,

//전역변수
int N = 0;
int M = 0;
vector<int> map[2001];
bool visited[2001];
int correct = 0;

int main() {
	cin >> N;
	cin >> M;
	for (int i = 0; i < M; i++) {
		int t1 = 0;
		int t2 = 0;
		cin >> t1 >> t2;
		map[t1].push_back(t2);
		map[t2].push_back(t1);
	}

양방향 그래프를 만들어 줍니다.

for (int i = 0; i < N; i++) {
		BT(i, 0);
		visited[i] = false;
		if (correct) { cout << "1";  break; }
}

for문을 돌면서 BT함수를 호출합니다.
모든 노드에서 전부 확인을 해봐야하는 이유는
0->1 2->3->4->5->6이라면 0번 1번노드에서 시작하는 경우는 조건을 만족하지 못하므로 2번에서 시작해야 조건을 만족 할 수 있기 때문입니다.

여기서 visited[i]로 만드는 이유는, BT메서드를 확인하면, 맨 처음 시작하는 노드를 방문처리를 하고 시작하는데, BT()메서드를 나오면, 해당 노드를 false로 만들어줘야, 노드 1번에서 다시 for문을 시작할때 노드 0번을 방문 할 수 있기 떄문입니다.

BT메서드를 호출하고 결과가 correct라면, 1을 호출하고 break를 겁니다. 왜냐하면 친구가 5명인 경우가 1가지만 있어도 되기 때문입니다.

void BT(int temp, int depth) {
	if (depth == 4) {
		correct = 1;
		return;
	}
	visited[temp] = true;

	for (int i = 0; i < map[temp].size(); i++) {
		if (!visited[map[temp][i]]) {
			BT(map[temp][i], depth + 1);
			visited[map[temp][i]] = false;
		}
	}
}

depth가 4면 correct를 1로 바꾸고 return문을 통해서 나옵니다.

시작 노드를 true로 설정하고 노드와 연결된 노드를 BT메서드를 다시 호출하여서 재귀 함수를 사용합니다.
다른 노드에서 방문을 할 수 있게 false로 바꿔줘야합니다.

최종코드,

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

int N = 0;
int M = 0;
vector<int> map[2001];
bool visited[2001];
int correct = 0;

void BT(int temp, int depth) {
	if (depth == 4) {
		correct = 1;
		return;
	}
	visited[temp] = true;

	for (int i = 0; i < map[temp].size(); i++) {
		if (!visited[map[temp][i]]) {
			BT(map[temp][i], depth + 1);
			visited[map[temp][i]] = false;
		}
	}
}
int main() {
	cin >> N;
	cin >> M;
	for (int i = 0; i < M; i++) {
		int t1 = 0;
		int t2 = 0;
		cin >> t1 >> t2;
		map[t1].push_back(t2);
		map[t2].push_back(t1);
	}
	for (int i = 0; i < N; i++) {
		BT(i, 0);
		visited[i] = false;
		if (correct) { cout << "1";  break; }
	}
	if(!correct){
		cout << "0";
	}
	return 0;
}