[SWEA] 4005 비밀

출처: [SWEA] SW 문제해결 심화 - 그래프

 Input 

1

10 6

6 3 1 5 7 6 10

5 10 8 3 5 2

4 6 10 3 1

5 10 5 7 9 8

5 6 10 2 3 4

7 5 2 1 3 7 10 9

 

 Output 

#1 2 2 4 0 2 1 3 1 1 5 10

 

- Test Case 개수 T / 정점의 개수 N /  간선 정보 개수 M

- M 줄에 거쳐 첫번째로는 간선의 개수 그 다음으로 연결되는 정점이 차례대로 주어집니다. (방향 그래프)

ex) 6 3 1 5 7 6 10   ← (1 ≤ Mi ≤ N)

    ▶ 6개 간선 정보: [3] → [1], [1] → [5], [5] → [7], [7] → [6], [6] → [10]

 

구현

M줄에 거쳐 주어지는 간선 정보들은, 일부분이거나 중복될 수 있기에

HashMap 구조를 이용해서 인접리스트 방식을 이용해 그래프 구현

완성된 유방향 그래프를 바탕으로

Out-Degree와 Longest path cost를 구할 수 있습니다.

※ 무방향 그래프에서 최장 경로를 구하는 문제 

    - [SWEA] 2814 최장경로 

[SWEA] 2814 최장경로

※ DFS의 경우에는 (2 ≤ N ≤ 10), (1 ≤ K ≤ 30)이므로 TLE 발생 X

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.StringTokenizer;
 
public class Solution {
    static int N, M;
    static List<List<Integer>> adList;
    static int maxPathCost;
     
    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());
            }
            HashMap<String, String> map = new HashMap<>();
            while(M-- > 0) {
                st = new StringTokenizer(br.readLine());
                int pathSize = Integer.parseInt(st.nextToken()); 
                // (문제조건)적어도 한명에게 비밀이 전달됩니다.
                int u = Integer.parseInt(st.nextToken());
                for(int i=1; i<pathSize; i++) {
                    int v = Integer.parseInt(st.nextToken());
                    String key = u + "_" + v; 
                    // 기존에 없던 간선인지 확인
                    if(!map.containsKey(key)) {
                        adList.get(u).add(v);
                        map.put(key, u+" to "+v);
                    }
                    u = v;
                }
            }
 
            maxPathCost = 0;
            // 각 정점을 출발 정점으로 설정해서 최장 경로 길이를 구합니다.
            for(int start = 1; start <= N; start++) {
                DFS(start, 1,  new boolean[N+1]);
            }
            System.out.print("#" + tc + " ");
            // i번 아이가 친하다고 생각하는 친구들의 수는
            // 정점에서 나가는 방향의 간선의 개수와 같습니다.
            for(int i=1; i<=N; i++) {
                System.out.print(adList.get(i).size() + " ");
            }
            System.out.println(maxPathCost);
        }
    }
     
    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;
        maxPathCost = Math.max(maxPathCost, cost);
    }
}