[백준 13023] ABCDE (C++)

문제 링크: https://www.acmicpc.net/problem/13023

13023번: ABCDE

1. 주의할 점

- DFS를 통해 해결한다

- 2000 X 2000 배열을 만들지 않고 List형태인 Vector를 사용한다

 

2. 구현

- 모든 Node를 시작점으로 각 지점까지의 거리가 4인 Node가 있다면 문제의 조건을 만족한다고 설정한다

- 모든 Node는 시작전에 시작점을 제외한 다른 Node의 Visit값을 False로 두고 시작한다.

- 현재 Node와 연결된 다른 Node를 방문한 적이 없다면 그 Node로 이동한다

 

#include <iostream>
#include <vector>
using namespace std;
vector<int> v[2000];
bool visit[2000];
bool avail = false;

void dfs(int idx, int cnt) {
	if (cnt == 4) {
		avail = true;
		return;
	}
	for (int i = 0; i < v[idx].size(); i++) {
		int next = v[idx][i];
		if (!visit[next]) {
			visit[next] = true;
			dfs(next, cnt + 1);
			visit[next] = false;
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int node, edge, s, e;
	cin >> node >> edge;
	for (int i = 0; i < edge; i++) {
		cin >> s >> e;
		v[s].push_back(e);
		v[e].push_back(s);
	}	
	for (int i = 0; i < node; i++) {
		for (int j = 0; j < node; j++)
			visit[j] = false;
		visit[i] = true;
		dfs(i, 0);
		if (avail) break;
	}
	if (avail) cout << 1;
	else cout << 0;
	system("pause");
	return 0;
}