SWEA 2814 최장 경로

1 개요

SWEA 2814 최장 경로

SW Expert 아카데미

#	문제	풀이

3 Java

import java.util.*;
public class Solution {
	static int N, M;
	static boolean[][] a;
	static int maxLength;
	static void addEdge(int v1, int v2) {
		a[v1][v2] = true;
		a[v2][v1] = true;
	}
	static void solve(int v, int len, boolean[] visit) {
		visit[v] = true;
		for(int i=1; i<=N; i++) {
			if( i == v ) continue;
			if( visit[i] ) continue;
			if( !a[v][i] ) continue;
			solve(i, len+1, visit);
			visit[i] = false;
		}
		if( len > maxLength ) maxLength = len;
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for(int tc=1; tc<=T; tc++) {
			N = sc.nextInt();
			M = sc.nextInt();
			a = new boolean[N+1][N+1];
			maxLength = 0;
			for(int i=1; i<=M; i++) addEdge(sc.nextInt(), sc.nextInt());
			for(int i=1; i<=N; i++) solve(i, 1, new boolean[N+1]);
			System.out.format("#%d %d\n", tc, maxLength);
		}
		sc.close();
	}
}

4 같이 보기

• 최장 경로 문제