N

(SWEA c++)2814. 최장경로 본문

SW Expert Academy

(SWEA c++)2814. 최장경로

naeunchan 2020. 10. 21. 11:05
728x90
반응형

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

 

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

swexpertacademy.com

 

DFS를 이용한 그래프 방문.

#include <iostream>

using namespace std;

int ans;
int N, M;
bool graph[11][11];
bool visited[11];

void dfs(int start, int current)
{
    if(ans < current)
        ans = current;
    
    for(int i = 1; i <= N; i++)
    {
        if(graph[start][i] && !visited[i])
        {
            visited[i] = true;
            dfs(i, current + 1);
            visited[i] = false;
        }
    }
}

int main(void)
{
    int t;
    cin >> t;
    
    for(int i = 1; i <= t; i++)
    {
        int x, y;
        cin >> N >> M;
        
        ans = 1;
        for(int j = 0; j <= N; j++)
        {
            visited[j] = false;
            for(int k = 0; k <= N; k++)
                graph[j][k] = false;
        }

        for(int j = 0; j < M; j++)
        {
            cin >> x >> y;
            graph[x][y] = true;
            graph[y][x] = true;
        }

        for(int j = 1; j <= N; j++)
        {
            visited[j] = true;
            dfs(j, 1);
            visited[j] = false;
        }
        
        cout << "#" << i << " " << ans << endl;
    }
    return 0;
}      
728x90
반응형

'SW Expert Academy' 카테고리의 다른 글

(SWEA c++)2948. 문자열 교집합  (0) 2020.10.21
(SWEA c++)2817. 부분 수열의 합  (0) 2020.10.21
(SWEA c++)2805. 농작물 수확하기  (0) 2020.10.21
(SWEA c++)2806. N-Queen  (0) 2020.10.20
(SWEA c++)1873. 상호의 배틀필드  (0) 2020.10.20