BOJ (C/C++) 13023번: ABCDE

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

13023번: ABCDE

---

풀이

문제 이해가 안 돼서 찾아보니 A~B~C~D~E의 관계가 있으면 되는 거라 DFS로 풀었다.

같은 출발지여도 중간에 어떤 사람을 선택하냐에 따라 최대 깊이가 달라지므로 선택한 사람을 거친 모든 경로 탐색 후 방문 표시를 없애주었다.

---

코드

#include <stdio.h>
#include <vector>
using namespace std;

vector<int> V[2001];
bool visited[2000], CAN = false;

void Is_Friend(int now, int cnt) {

	// A-B-C-D-E 의 경로가 존재함
	if (cnt == 5) {
		CAN = true;
		return;
	}

	for (int i = 0; i < V[now].size(); i++) {
		// 다음에 방문할 사람
		int next = V[now][i];

		if (!visited[next]) { // 방문하지 않은 사람이라면

			visited[next] = true;
			Is_Friend(next, cnt + 1);

			// 해당 사람을 거친 모든 경로 확인 후 방문 표시 삭제
			visited[next] = false;
		}
	}
}

int main() {
	int M, N, a, b;

	// input
	scanf("%d %d", &N, &M);
	for (int i = 0; i < M; i++) {
		scanf("%d %d", &a, &b);
		V[a].push_back(b);
		V[b].push_back(a);
	}

	for (int i = 0; i < N; i++) { // 몇 번에서 시작해야 깊이 5의 경로가 나올 지 모르므로 모든 노드 다 시도
		visited[i] = true;
		Is_Friend(i, 1);

		// 깊이 5가 나왔다면 1 출력 후 프로그램 종료
		if (CAN) {
			printf("1");
			return 0;
		}

		// init
		fill(visited, visited + N, false);
	}

	printf("0");
	return 0;
}