글 읽기 - 그래프의 깊이로 문제를 해결하고자 합니다.

ckdhyeon95 4년 전 0

모든 정점을 root로 한번씩 순회하며 dfs탐색을 하여, 그래프의 최대 깊이가 5이상이 되는 경우가 있다면 true 아니면 false라고 생각했습니다.

따라서 dfsAll 함수에서 모든 정점에 대해 dfs탐색을 시작하기 전 visited 배열을 false로 초기화해줬고, dfs함수에서는 그래프의 최대 깊이를 반환하도록 하였습니다.

그런데 틀렸습니다가 나옵니다.

제 알고리즘에 오류가 있는지 알고싶습니다.

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

bool visited[2000];
int inputN, inputM;
vector<vector<int> > adj(2000);

// 그래프의 최대 깊이 반환
int dfs(int pos, int depth) {

	visited[pos] = true;

	int ret = depth;

	for (int i = 0; i < adj[pos].size(); ++i) {
		int nextPos = adj[pos][i];
		if (visited[nextPos])
			continue;
		ret = max(ret, dfs(nextPos, depth + 1));
	}

	return ret;
}

bool dfsAll() {

	bool ret = false;

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

		memset(visited, false, sizeof(visited));
		if (dfs(i, 1) >= 5)        // 한번이라도 최대 깊이 반환값이 5 이상이라면
			ret = true;            // true

	}

	return ret;

}

int main() {

	cin >> inputN >> inputM;

	for (int i = 0; i < inputM; ++i) {
		int n1, n2;
		cin >> n1 >> n2;
		adj[n1].push_back(n2);
		adj[n2].push_back(n1);
	}

	bool check = dfsAll();

	if (check)
		cout << 1;
	else
		cout << 0;

	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

그래프의 깊이로 문제를 해결하고자 합니다.

ckdhyeon95 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말