[SWEA - Java] 2814 : 최장 경로

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7GOPPaAeMDFAXB 

SW Expert Academy

전체 코드

dfs를 하되, 각 정점마다 dfs를 모두 해보면서 최장 경로를 따져봐야 한다.

그렇기에 dfs후에 정점 인덱스에 해당하는 visited 값을 false로 만들어주어야 한다.

(아예 dfs를 시작할 for문 안에서 visited를 초기화해주어도 된다.)

 

그리고 갔다 온 정점은 visited의 값이 true인데

이것 역시 재귀가 종료될 때 false로 만들어주어야지 최장 경로 구할 수 있음

 

import java.util.Scanner;

class Solution
{
	public static int[][] map;
	public static boolean[] visited;
	public static int max;
	public static int n;

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

		for(int test_case = 1; test_case <= T; test_case++)
		{
			max = Integer.MIN_VALUE;
			int N = sc.nextInt();
			int M = sc.nextInt();
			n = N;

			map = new int[N+1][N+1];
			visited = new boolean[N+1];

			for(int i = 0; i < M; i++) {
				int n1 = sc.nextInt();
				int n2 = sc.nextInt();
				map[n1][n2] = map[n2][n1] = 1;
			}

			for(int i = 1; i < N+1; i++) {
			//여기서 visited 배열을 초기화 시켜주면 아래 36줄의 visited[i] = false 문 필요없음 
            		//visited = new boolean[N+1]; 
				dfs(1, i);
				visited[i] = false;
			}

			System.out.println("#" + test_case + " " + max);
		}
	}

	public static void dfs(int cnt, int v) {
		visited[v] = true;

		for(int i = 0; i < n+1; i++) {
			if(map[v][i] == 1 && !visited[i]) {
				dfs(cnt+1, i);
				visited[i] = false;
			}
		}	
		max = Math.max(cnt, max);
	}
}