boj, 백준) 13023. ABCDE ( C / C++ )

1. 문제 링크

www.acmicpc.net/problem/13023

13023번: ABCDE

 

2. 문제 개요

사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다.

A는 B와 친구다.

B는 C와 친구다.

C는 D와 친구다.

D는 E와 친구다.

위와 같은 관계가 존재하는지 안 하는지 구하는 프로그램을 작성하시오.

 

오랜만에 DFS문제를 풀었는데  처음 생각을 잘못해서 10%쯤에서 계속 틀렸다..

끙끙 앓다가 풀고 나니 허탈한 문제.

3. 문제 힌트

예외

결국 문제의 의미는 4번 연속으로 연결되는, DFS를 할 때 깊이가 4인 것이 단 한 개라도 있으면 1을 출력하면 된다.

위의 가장 왼쪽의 빨간색 노드에서 출발할 때, 파란색 간선을 따라 DFS가 실행된다면 바로 찾을 것이다.

하지만 DFS를 할때 빨간색 간선을 먼저 탐색해버리면 해가 있음에도 불구하고 찾을 수 없다.

이런 경우에는 어떻게 처리해야 할까??

방문처리를 하면 안 될 거 같은데..

 

4. 문제 풀이

그냥 방문처리를 아예 안 해주면 시간 복잡도가 너무 늘어나서 시간 초과가 날것이다.

그래서 방문을 하면서 depth가 4가 넘는지 체크하고 스택을 따라 return 할 때, 방문처리를 다시 삭제해줌으로써 3번의 예외상황인 경우에도 해를 찾을 수 있게 해주자.

 

 

5. 코드

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

vector<vector<int>> adj;
vector<bool> visited;
int n, m;
bool ans = false;

void dfs(int depth, int cur)
{
	visited[cur] = true;
	if (depth == 4)
	{
		ans = true;
		return;
	}

	for (int next : adj[cur]) {
		if (ans)	return;
		if (!visited[next])
			dfs(depth + 1, next);
	}

	visited[cur] = false;
	return;
}

int main()
{
	scanf("%d %d", &n, &m);
	adj.resize(n);
	visited.resize(n);

	for (int i = 0; i < m; ++i) {
		int from, to;
		scanf("%d %d", &from, &to);

		adj[from].push_back(to);
		adj[to].push_back(from);
	}



	for (int i = 0; i < n; ++i) {

		int maxdist = 0;
		fill(visited.begin(), visited.end(), false);
		dfs(0, i);

		if (ans) {
			printf("1\n");
			return 0;
		}
	}

	printf("0\n");

	return 0;
}

 

 

6. 결과