[JAVA] SWEA 2814 - 최장 경로

solution

한번 방문한 정점은 다시 방문할 수 없기 때문에 dfs로 짜야 한다.
bfs로 풀면 한번 방문한 정점을 다시 방문하게 된다.
테스트 케이스를 직접 그려서 확인해 보면 어떤 정점을 먼저 방문할지에 따라 경로의 길이가 달라지는 것을 알 수 있다. 예를 들어 입력 데이터가 아래와 같다면

1
3 2
1 2
3 2

1번 정점부터 시작할 경우 1-3, 또는 1-2로 최장 경로 길이는 2이다.
하지만 3번 정점부터 시작할 경우 3-1-2로 최장 경로 길이는 3이다.
어떤 정점을 먼저 방문하는지에 따라 경로의 길이가 달라지게 된다.
1번 정점에서 시작하는 최장 경로 길이는 또 1번 다음 출발 정점(=a) + a에서 출발하는 최장 경로 길이 이런 식으로 재귀적으로 구해 나갈수 있다.
이런 식으로 1-N까지 각 정점에서 시작하는 최장 경로를 구해서 최댓값을 출력해 주면 된다.

code

import java.util.*;
class Solution
{
     static int max = 0;

	public static void main(String args[]) throws Exception
	{
		Scanner sc = new Scanner(System.in);

        StringBuffer sb = new StringBuffer();

        int T = sc.nextInt();
        for(int tc=1; tc<=T; tc++){
            sb.append("#").append(tc).append(" ");
           
            int N = sc.nextInt();
            int M = sc.nextInt();

            ArrayList<Integer> edges[] = new ArrayList[N+1];
            for(int i=1; i<=N; i++){
                edges[i] = new ArrayList<>();
            }

            for(int i=0; i<M; i++){
                int a = sc.nextInt();
                int b = sc.nextInt();
                edges[a].add(b);
                edges[b].add(a);
            }
            max = 0;
            for(int i=1; i<=N; i++){
                boolean check[] = new boolean[N+1];
                check[i] = true;
                int cmp = solve(edges,check,i) + 1;
                max = Math.max(max,cmp);
            }
            sb.append(max).append("\n");

        }
        System.out.println(sb);
	}
    static int solve(ArrayList<Integer> edges[], boolean check[], int cur){
        int count = 0;
        int ret = 0;
        for(int i=0; i<edges[cur].size(); i++){
            int nxt = edges[cur].get(i);
            if(check[nxt])
                continue;
            check[nxt] = true;
            count += solve(edges, check, nxt) + 1;
            ret = Math.max(ret,count);
            check[nxt] = false;
            
            count = 0;
            
        }
        return ret;

    }
}