[C++] SWEA 2814 - 최장 경로

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

SW Expert Academy

<풀이>

1. 정점 개수와 간선 정보를 입력받는다.

2. 한 정점에서 다른 정점으로 갈 수 있는 최장 경로를 계산하여 출력한다.

 

<해법>

1. 최장 경로를 계산하는 방법

=> 어떤 정점에서 출발해야하는지 모르기 때문에, 모든 정점에서 출발해보아야 합니다. 따라서, 모든 정점에서 출발하여 겹치지 않고 갈 수 있는 정점까지 가서 최장경로를 계산합니다.

 

#include <iostream>
#include <string.h>
 
using namespace std;
 
int N, M;
int edge[11][11];
bool visited[11];
int answer;
 
void findLongestPath(int index, int pathCount) {
 
    //결과 갱신
    if (pathCount > answer) {
        answer = pathCount;
    }
 
    //현재 정점에서 갈 수 있는 모든 정점 가보기
    for (int i = 1; i <= N; i++) {
 
        //간선이 있고, 이전에 방문한 적이 없는 경우 -> 방문
        if (edge[index][i] && !visited[i]) {
            visited[i] = true;
            findLongestPath(i, pathCount + 1);
            visited[i] = false;
        }
    }
}
 
int main() {
 
    int test_case;
    int T;
 
    cin >> T;
 
    for (test_case = 1; test_case <= T; test_case++) {
 
        //초기화
        N = 0, M = 0;
        memset(edge, 0, sizeof(edge));
        memset(visited, false, sizeof(visited));
        answer = 0;
 
        //입력
        cin >> N >> M;
        for (int i = 0; i < M; i++) {
            int x, y;
            cin >> x >> y;
            
            //간선 정보 등록
            edge[x][y] = 1;
            edge[y][x] = 1;
        }
 
        //해법
        /*
        1번 정점부터 N번 정점까지 모두 최장경로 찾기
        */
        for (int i = 1; i <= N; i++) {
            visited[i] = true;
            findLongestPath(i, 1);
            visited[i] = false;
        }
 
        //출력
        cout << "#" << test_case << " " << answer << "\n";
    }
 
    //종료
    return 0;
}

 

브루트포스에 대해 알아볼 수 있는 문제였습니다.