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

[문제보기]

  최장 경로

SW Expert Academy

 

[풀이과정]

1. dfs()

  (1) dfs알고리즘을 사용

      파라미터로 node와 sum을 받아 사용

  (2) node는 현재 정점을 나타내고, sumd은 처음 시작하는 node에서 최대 경로를 나타냅니다.

  (3) 각 node의 간선의 데이터를 가지고 있는 vector v를 사용하여 dfs()를 진행 한번 지나온 node에 대해서는

       check 배열을 사용하여 다시 못 지나가게 해 준다.

 

 2. main()

  (1) 정점의 데이터를 나타내는 n만큼 vector v를 생성 및 초기화해준 후 간선에 대한 데이터를 v에 넣어준다

       -> 이때, 무방향 그래프이기 때문에, x, y에 대해서 두 번 간선의 데이터를 넣어주어야 한다.

  (2) for문을 이용하여 생성된 각 node에 대해서 dfs()를 실행해준다.

 

[소스코드]

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
int n, m;
vector<vector<int>> v;
bool check[11];
int ans;

void dfs(int node, int sum){
    check[node] = false;
    for(int i=0; i<v[node].size(); i++){
        int next = v[node][i];
        if(check[next]){
            dfs(next, sum+1);
        }
    }

    check[node] = true;
    ans = max(ans, sum);
}

int main(){
    cin.tie(0);
    cout.sync_with_stdio(false);
    int T;
    cin >> T;
    for(int test = 1; test <= T; test++){
        memset(check, false, sizeof(check));
        ans = 0;
        cin >> n >> m;
        v = vector<vector<int>>(n+1,vector<int>());
        for(int i=1; i<=n; i++){
            check[i] = true;
        }

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

        for(int i=1; i<=n; i++){
            dfs(i,1);
        }
        cout << "#" << test <<" " << ans << "\n";

    }
}

 

[해결 과정 중 실수한 부분]