[SWEA] - 2814. 최장 경로 (D3)

[문제]

N개의 정점과 M개의 간선으로 구성된 가중치가 없는 무방향 그래프에서의 최장 경로의 길이를 계산하자.
정점의 번호는 1번부터 N번까지 순서대로 부여되어 있다.
경로에는 같은 정점의 번호가 2번 이상 등장할 수 없으며, 경로 상의 인접한 점들 사이에는 반드시 두 정점을 연결하는 간선이 존재해야 한다.
경로의 길이는 경로 상에 등장하는 정점의 개수를 나타낸다.

[입력]
첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스의 첫 번째 줄에는 두 개의 자연수 N M(1 ≤ N ≤ 10, 0 ≤ M ≤ 20)이 주어진다.
두 번째 줄부터 M개의 줄에 걸쳐서 그래프의 간선 정보를 나타내는 두 정수 x y(1 ≤ x, y ≤ N)이 주어진다.
x와 y는 서로 다른 정수이며, 두 정점 사이에 여러 간선이 존재할 수 있다.

[출력]
각 테스트 케이스마다 ‘#x ’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고, 그래프에서의 최장 경로의 길이를 출력한다.

문제 풀기

2814. 최장 경로

 

---

[풀이]

• dfs 알고리즘을 사용하여 풀이
• n번째 정점에서 시작하는 최장경로 길이를 재귀적으로 구하여 최댓값 출력

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 = sc.nextInt();
		
		for(int tc=1; tc<=t; tc++) {
			max = Integer.MIN_VALUE;
			
			n = sc.nextInt();
			int m = sc.nextInt();
			
			map = new int[n+1][n+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+1; i++) {
				visited = new boolean[n+1];
				dfs(1, i);
			}
			
			System.out.format("#%d %d\n", tc, 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);
	}
}