[C++] 백준 13023: ABCDE

문제

[C++] 백준 13023: ABCDE GOLD 5
https://www.acmicpc.net/problem/13023

 

---

 

접근 방법

이 문제는 사람 관계가 주어졌을 때, 서로 연속으로 연결된 5명(A–B–C–D–E) 이 존재하는지를 판단하는 문제이다.

처음에 이 부분을 이해 못 해서 헤맸다;;
즉, 그래프에서 길이 4의 경로(간선)가 하나라도 있으면 1, 없으면 0을 출력한다.

 

무방향 그래프이므로 친구 관계 (a, b)는 양방향으로 저장한다.
각 정점을 시작점으로 삼아 DFS를 수행하면서,
현재까지 연결된 사람 수(cnt)가 4가 되는 순간 4개의 조건을 만족한 것이므로 탐색을 종료한다. 

• 간선이 4개 = 노드가 5개 → 조건 만족

if (cnt == 4)  // 4가지 조건 모두 만족 시
{
	flag = true;
	return;
}

 

구현 시 주의할 점

• visited[node] = false 처리가 매우 중요하다.
  DFS가 끝난 뒤 방문 표시를 되돌려야, 다른 경로에서 해당 노드를 다시 사용할 수 있다.
  이 처리를 하지 않으면 이전 탐색의 방문 상태가 남아 정상적인 경로 탐색이 불가능해진다.

 

---

 

코드

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

vector<vector<int>> friends;
vector<bool> visited;
bool flag;

void dfs(int node, int cnt)  // 현재 노드, 조건 만족 수
{
	if (cnt == 4)  // 4가지 조건 모두 만족 시
	{
		flag = true;
		return;
	}

	visited[node] = true;
	
	for (int i = 0; i < friends[node].size(); i++)
	{
		int next = friends[node][i];
		if (visited[next] == false)
			dfs(next, cnt + 1);
	}
	visited[node] = false;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N = 0, M = 0;
	cin >> N >> M;

	friends.resize(N);
	visited.resize(N, false);
	for (int i = 0; i < M; i++)
	{
		int a = 0, b = 0;
		cin >> a >> b;

		friends[a].push_back(b);
		friends[b].push_back(a);
	}

	for (int i = 0; i < N; i++)
	{
		dfs(i, 0);

		if (flag == true)
			break;
	}
	if (flag == false)
		cout << 0;
	else
		cout << 1;

	return 0;
}