[SW expert Academy] SWEA 2814번 최장경로 자바(Java)

[D3] 최장 경로 - 2814

문제 링크

성능 요약

메모리: 22,336 KB, 시간: 147 ms, 코드길이: 1,182 Bytes

제출 일자

2023-10-28 15:33

출처: SW Expert Academy, https://swexpertacademy.com/main/code/problem/problemList.do

import java.util.Scanner;
class Solution
{
    static int[][] map;
    static boolean[] visit;
    static int result;
	public static void main(String args[]) throws Exception
	{
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for(int tc = 1; tc <= T; tc++)
		{
            int n = sc.nextInt();
            int m = sc.nextInt();
            map = new int[n+1][n+1];
            visit = new boolean[n+1];
            result = 0;
            for(int i = 0; i <= n; i++){
                map[i][i] = 1;
            }
            for(int i = 0; i < m; i++){
                int a = sc.nextInt();
                int b = sc.nextInt();
                map[a][b] = map[b][a] = 1;
            }
            for(int i = 1; i <= n; i++){
                solution(i,0);
            }
            System.out.println("#" + tc + " " + result);
		}
	}
    
    private static void solution(int pos, int count){
        for(int i = 1; i < map.length; i++){
            if(!visit[i] && map[pos][i] == 1){
                visit[i] = true;
                solution(i,count+1);
                visit[i] = false;
            }
        }
        result = Math.max(result, count);
    }
}