글 읽기 - 어디가 틀린지 모르겠습니다. DFS로 시도하였습니다

nongman25 4년 전 0

dfs로 어떤 정점으로부터 거리 2이내인 정점 개수의 최대값을 구하였는데 정답은 계속틀렸다고 하네요. 어디서 무엇을 놓친지 잘 모르겠어서 질문드립니다.

#include <iostream>
#include <vector>
#include <array>

using namespace std;

typedef vector<int> vi;

int DFS(int s, bool* visited, vi* adj,int dis,int sou)
{
	visited[s] = 1;
//	cout << sou << "is 2-friend with " << s<<endl;
	if (dis == 2)
		return 1;

	int low_val = 0;
	for (auto i = adj[s].begin(); i != adj[s].end(); ++i)
		if (!visited[*i])
			low_val += DFS(*i, visited, adj, dis + 1,sou);
	if (dis)
		low_val++;
	/*
	if (!dis)
		cout << s << "'s val = " << low_val << endl;
	*/
	return low_val;
}

int main()
{
	int n;
	cin >> n;
	vi* adj = new vi[n];

	for (int i = 0; i < n; i++)
	{
		char* tm = new char[n + 1];
		cin >> tm;
		for (int j = 0; j < n; j++)
		{
			if (tm[j] == 'Y')
				adj[i].push_back(j);
		}
		delete [] tm;
	}

	int max = 0;

	bool* visited = new bool[n];
	for (int i = 0; i < n; i++)
	{
		for (int k = 0; k < n; k++)
			visited[k] = 0;
		int tmax = DFS(i,visited,adj,0,i);
		max = std::max(max, tmax);
	}
	cout << max << endl;

	delete[] visited;
	delete[] adj;
}

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

문제

문제

출처

ICPC

어디가 틀린지 모르겠습니다. DFS로 시도하였습니다

nongman25 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말