[SWEA] (C++) D3 2814 최장 경로

그래프 완전 탐색 문제이며, DFS BFS로 풀 수 있다.

그 중 DFS로 풀었으며 방향성이 없기 때문에 GRAPH의 양쪽 node 모두에 저장한다.

start node에서 현재 node의 len을 알려주는 매개변수가 필요하며 , len과 max값인 cnt를 비교하여 제일 긴 길이를 저장한다.

#include<iostream>
#include<vector>

using namespace std;

int cnt;
bool visited[11] = { false };

void DFS(vector<vector<int>> g, int index, int len)
{
	visited[index] = true;

	if (cnt < len)
		cnt = len;

	for(int i = 0; i < g[index].size(); i++)
		if (!visited[g[index][i]])
			DFS(g, g[index][i], len + 1);

	visited[index] = false;
}

int main(int argc, char** argv)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int test_case;
	int T;

	cin >> T;

	for (test_case = 1; test_case <= T; ++test_case)
	{
		cnt = 1;
		int N, M; cin >> N >> M;
		vector<vector<int>> GRAPH(N + 1, vector<int>());

		int x, y;
		for (int i = 0; i < M; i++)
		{
			cin >> x >> y;
			GRAPH[x].push_back(y);
			GRAPH[y].push_back(x);
		}

		for (int i = 1; i <= N; i++)
			DFS(GRAPH, i, 1);

		cout << '#' << test_case << ' ' << cnt << '\n';
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}