C++ SWEA 2814. 최장 경로

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7GOPPaAeMDFAXB&

SW Expert Academy

풀이

이 문제 푸는데 2시간정도..? 결국 test_case 10개 중 8개까지 맞췄는데 2개는 뭔들 ,, 생각안나서 그냥 다른 분들 코드 참고해서 풀었다,, 어렵다 증말,,

 

DFS 형식으로 풀었으며 1~N까지 하나씩 순회하면서 , 최장길이를 찾는 알고리즘을 짰다.

 

문제 댓글에서 반례를 보고 나서

 

DFS끝나면 방문체크를 다시 False를 하는 것을 추가해주었다 .

---

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
vector <int> v[11];
int visited[11] = { 0, };
int long_edge = 0;

void dfs(int x, int count) {
	if (count > long_edge) long_edge = count; 

	for (int i = 0; i < v[x].size(); i++) {
		int y = v[x][i];
		if (!visited[y]) { // 방문안했으면 
			visited[y] = 1; 
			dfs(y, count + 1);
			visited[y] = 0;
		}
	}
}

int main(){
	int t_c = 0; cin >> t_c;
	for (int i = 0; i < t_c; i++) {
		int N, M; // N : 정점의 번호, M : 간선
		cin >> N >> M;
		for (int j = 0; j < M; j++) {
			int x, y;
			cin >> x >> y;
			v[x].push_back(y);
			v[y].push_back(x);
		}
		for (int i = 1; i <=N; i++) { // 각 요소별 dfs 돌리면서 최장 길이 찾기
			visited[i] = 1;
			dfs(i,1);
			memset(visited, 0, sizeof(visited));
		}
		cout << "#" << i + 1 << " " << long_edge << endl;
		memset(v, 0, sizeof(v));
		long_edge = 0;
	}
	return 0;
}