그래프 완전 탐색 문제이며, 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을 리턴해야합니다.
}
'Coding_Test 연습 > SWEA' 카테고리의 다른 글
[SWEA] (C++) D3 1860 진기의 최고급 붕어빵 (0) | 2022.04.08 |
---|---|
[SWEA] (C++) D3 1873 상호의 배틀필드 (0) | 2022.04.08 |
[SWEA] (C++) D3 2806 N-Queen (0) | 2022.04.07 |
[SWEA] (C++) D3 2805 농작물 수확하기 (0) | 2022.04.07 |
[SWEA] (C++) D3 2817 부분 수열의 합 (0) | 2022.04.07 |