[SWEA] 2814 최장경로

출처: [SWEA] 문제 링크

 Input 

2

1 0

3 2

1 2

3 2

 

 Output 

#1 1

#2 3 

첫번째 Case는 간선 없이 정점 한개 존재하므로, 최장 경로의 길이 = 1　

두번째 Case는 [3] - [2] - [1] or [1] - [2] - [3], 최장 경로의 길이 = 3

 

출발 정점을 [1] ~ [N]으로 해서 연결된 모든 간선을 DFS 탐색하여 최장 경로의 길이를 구합니다.

private static void DFS(int current, int cost, boolean[] visited) {
    visited[current] = true;
    // 정점 [current]와 연결된 정점 리스트
    List<Integer> to = adList.get(current);
    for(int i = 0; i < to.size(); i++) {
        int next = to.get(i);
        if(!visited[next]) {
            DFS(next, cost + 1, visited);
            visited[next] = false;
        }
    }
    visited[current] = false;
    answer = Math.max(answer, cost);
}

 

Sample Case

 Input 

1

6 5

1 2

1 3

2 4

2 5

2 6

 

 Output 

#1 4

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
 
public class Solution {
    static int N, M;
    static List<List<Integer>> adList;
    static int answer;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
 
        int T = Integer.parseInt(br.readLine());
 
        for (int tc = 1; tc <= T; tc++) {
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken()); // 정점의 개수
            M = Integer.parseInt(st.nextToken()); // 간선의 개수
             
            adList = new ArrayList<>();
            // 인덱스를 1부터 하기 위해 임의로 한 개를 넣어둠  
            adList.add(new<Integer> ArrayList());
            for(int i=1; i<=N; i++) {
                adList.add(new<Integer> ArrayList());
            }
             
            while(M-- > 0) {
                st = new StringTokenizer(br.readLine());
                int u = Integer.parseInt(st.nextToken());
                int v = Integer.parseInt(st.nextToken());
                // 무방향 그래프이므로 양 정점에 간선 정보 저장.
                adList.get(u).add(v);
                adList.get(v).add(u);
            }
            answer = 0;
            // 각 정점을 출발 정점으로 설정해서 최장 경로 길이를 구합니다.
            for(int start = 1; start <= N; start++) {
                DFS(start, 1,  new boolean[N+1]);
            }
            System.out.println("#" + tc + " " + answer);
        }
    }
     
    private static void DFS(int current, int cost, boolean[] visited) {
        visited[current] = true;
        // 정점 [current]와 연결된 정점 리스트
        List<Integer> to = adList.get(current);
        for(int i = 0; i < to.size(); i++) {
            int next = to.get(i);
            if(!visited[next]) {
                DFS(next, cost + 1, visited);
                visited[next] = false;
            }
        }
        visited[current] = false;
        answer = Math.max(answer, cost);
    }
}