[C++] 백준 13023 ABCDE

#include <iostream>
#include <vector>

using namespace std;

bool visited[2000]{ false };
bool result = false;

void dfs(int currNode, int count, const vector<vector<int>>& friends)
{
	if (count == 4)
	{
		result = true;
		return;
	}

	for (int i = 0; i < friends[currNode].size(); ++i)
	{
		int nextNode = friends[currNode][i];

		if (visited[nextNode])
		{
			continue;
		}

		visited[nextNode] = true;

		dfs(nextNode, count + 1, friends);

		visited[nextNode] = false;
	}
}

int main()
{
	int n, m;
	cin >> n >> m;

	vector<vector<int>> friends(n);

	for (int i = 0; i < m; ++i)
	{
		int a, b;
		cin >> a >> b;

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

	for (int i = 0; i < m; ++i)
	{
		visited[i] = true;

		for (int j = 0; j < friends[i].size(); ++j)
		{
			int nextNode = friends[i][j];

			visited[nextNode] = true;

			dfs(nextNode, 1, friends);

			visited[nextNode] = false;
		}

		if (result)
		{
			break;
		}

		visited[i] = false;
	}

	cout << result;

	return 0;
}

 

문제 풀이

1. 친구 입력을 어떻게 넣을 것 인가에 먼저 초점을 잡았고 처음에는 pair로 하나씩 넣을까하다가 원하는 시작점에 바로 접근하기에 어렵다고 판단해서 vector로 넣었다.

2. 친구의 관계가 유형4를 보면 양방향으로 들어갈 수 있으므로 양방향으로 입력

3. 특정 시작점이 없으므로 시작점이 있고 다음 도착점이 있는 곳을 dfs하였다.

4. dfs안에서도 동일 방법으로 찾게 하고 친구관계가 A,B,C,D,E가 각자 다른 친구 관계를 가지면서도 이어진 친구관계이면 된다로 판단하고 4개의 관계가 있으면 친구관계가 형성됐다고 판단하게 한다.

 

느낀점

1. 입력 실수와 dfs와 bfs중 뭐가 더 좋을지에 대한 빠른 판단력을 더 키워야할 것 같다.

2. 문제 해독하는 시간을 중요한 점을 빠르게 캐치하는 연습을 해야될 듯하다.

 

 

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

13023번: ABCDE