SWEA 2814: 최장 경로 (C++)

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

모든 정점을 시작점으로 dfs를 돌려주면 된다.

#include<iostream>
 
using namespace std;
 
int grp[11][11]; //1-indexed
bool vis[11]; //방문처리
int n, m, Max = 1;
 
void dfs(int len, int cur) {
    vis[cur] = true;
 
    if (Max < len) Max = len;
    for (int i = 1; i <= n; i++) {
        if (grp[cur][i] == 1 && !vis[i])
            dfs(len + 1, i);
    }
    vis[cur] = false;
}
 
void initGrp() {
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            grp[i][j] = 0;
}
 
int main(void) {
 
    int T;
    cin >> T;
    for (int tc = 1; tc <= T; tc++) {
        
        cin >> n >> m;
        
        for (int i = 0; i < m; i++) {
            int src, dst;
            cin >> src >> dst;
            
            grp[src][dst] = 1;
            grp[dst][src] = 1;
            
        }
 
        for (int i = 1; i <= n; i++) 
            dfs(1, i); // i번 정점에서 길이 
        
        printf("#%d %d\n", tc, Max);
        Max = 1;
        initGrp();
    }
 
    return 0;
}

방문 처리를 조금 더 직관적으로 하면 다음과 같이 구현할 수 있다.

#include<iostream>
 
using namespace std;
 
int grp[11][11]; //1-indexed
bool vis[11]; //방문처리
int n, m, Max = 1;
 
void dfs(int len, int cur) {
    //vis[cur] = true;
 
    if (Max < len) Max = len;
    for (int i = 1; i <= n; i++) {
        if (grp[cur][i] == 1 && !vis[i]) {
            vis[i] = true;
            dfs(len + 1, i);
            vis[i] = false;
        }
    }
    //vis[cur] = false; //확인이 끝난 점은 방문을 해제
}
 
void initGrp() {
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            grp[i][j] = 0;
}
 
int main(void) {
 
    int T;
    cin >> T;
    for (int tc = 1; tc <= T; tc++) {
        
        cin >> n >> m;
        
        for (int i = 0; i < m; i++) {
            int src, dst;
            cin >> src >> dst;
            
            grp[src][dst] = 1;
            grp[dst][src] = 1;
            
        }
 
        for (int i = 1; i <= n; i++) {
            vis[i] = true;
            dfs(1, i); // i번 정점에서 길이
            vis[i] = false;
        }
        
        printf("#%d %d\n", tc, Max);
        Max = 1;
        initGrp();
    }
 
    return 0;
}