TIL

2023.09.17 (SUN)

그래프 - 인접 리스트

/*
 * Title : 상근이의 여행
 * Link : https://www.acmicpc.net/problem/9372
 */
import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int result[];

        // input
        int tc = Integer.parseInt(br.readLine());
        result = new int[tc];

        // each TestCase
        for (int t = 0; t < tc; t++) {
            int answer = Integer.MAX_VALUE;
            st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());

            // input & 인접 리스트
            ArrayList<ArrayList<Integer>> graph = new ArrayList<>();

            for (int i = 0; i <= N; i++)
                graph.add(new ArrayList<>()); // 각 노드 별 리스트를 만든다.
            for (int i = 0; i < M; i++) { // make graph
                st = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());

                putEdge(graph, x, y);
            }

            for (int i = 0; i < N ; i++) {
                int check = checkEdge(graph, i);
                if (check < answer) {
                    answer = check;
                }
            }
            
            result[t] = answer;
        }

        for (int r:result) 
            System.out.println(r);
    }

    public static void putEdge(ArrayList<ArrayList<Integer>> graph, int x, int y) {
        graph.get(x).add(y);
        graph.get(y).add(x);
    }

    public static int checkEdge(ArrayList<ArrayList<Integer>> graph, int x) {
        
    }
}

그래프를 표현할 때, 가장 효율적인 방법인 듯

신장 트리 / 최소 신장 트리 (MST)

신장 트리란 : 그래프의 모든 정점을 사이클 없이 잇는 트리

최소 신장 트리 : 신장 트리에서 간선의 가중치의 합이 최소가 되는 트리

MST는 내일 다루도록 해보고, 오늘은 신장트리를 구현하였다.