삼성 SDS 대학생 알고리즘 특강 8일차 - 그래프

3176: 도로 네트워크

import java.util.*;
import java.io.*;

class Main {
    static int N, D, depth[], dp[][], min[][], max[][];
    static List<int[]> adj[];

    static void bfs(int root) {
        Queue<Integer> q = new LinkedList<>();
        q.add(root);
        depth[root] = 1;
        while(!q.isEmpty()) {
            int curr = q.poll();
            for(int i = 0; i < adj[curr].size(); i++) {
                int[] next = adj[curr].get(i);
                int nv = next[0];
                int w = next[1];
                if(depth[nv] > 0) continue;
                dp[0][nv] = curr;
                max[0][nv] = min[0][nv] = w;
                depth[nv] = depth[curr] + 1;
                q.add(nv);
            }
        }
    }
    static int[] lca(int u, int v) {
        int min_ = Integer.MAX_VALUE, max_ = Integer.MIN_VALUE;
        if(depth[u] > depth[v]) {
            int temp = u;
            u = v;
            v = temp;
        }
        int diff = depth[v] - depth[u];
        for(int i = 0; i <= D; i++) {
            if(((1 << i) & diff) > 0) {
                min_ = Math.min(min_, min[i][v]);
                max_ = Math.max(max_, max[i][v]);
                v = dp[i][v];
            }
        }
        if(u != v) {
            for(int i = D-1; i >= 0; i--) {
                if(dp[i][u] != dp[i][v]) {
                    min_ = Math.min(min_, Math.min(min[i][u], min[i][v]));
                    max_ = Math.max(max_, Math.max(max[i][u], max[i][v]));
                    u = dp[i][u];
                    v = dp[i][v];
                }
            }
            min_ = Math.min(min_, Math.min(min[0][u], min[0][v]));
            max_ = Math.max(max_, Math.max(max[0][u], max[0][v]));
        }
        return new int[] {min_, max_};
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        for(; (1 << D) < N; D++);
        depth = new int[N+1];
        dp = new int[D][N+1];
        min = new int[D][N+1];
        max = new int[D][N+1];
        adj = new ArrayList[N+1];

        for(int i = 1; i <= N; i++) {
            adj[i] = new ArrayList<>();
        }

        for(int i = 1; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            adj[u].add(new int[] {v, w});
            adj[v].add(new int[] {u, w});
        }
        //tree 생성
        bfs(1);
        //sparse table 생성
        for(int j = 1; j < D; j++) {
            for(int i = 1; i <= N; i++) {
                dp[j][i] = dp[j-1][dp[j-1][i]];
                min[j][i] = Math.min(min[j-1][i], min[j-1][dp[j-1][i]]);
                max[j][i] = Math.max(max[j-1][i], max[j-1][dp[j-1][i]]);
            }
        }
        int K = Integer.parseInt(br.readLine());
        for(int k = 0; k < K; k++) {
            st = new StringTokenizer(br.readLine());
            int res[] = lca(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
            bw.write(res[0] + " " + res[1] + "\n");
        }
        bw.close();
    }
}

 

 

3830: 교수님은 기다리지 않는다

import java.io.*;
import java.util.*;

public class Main {
    static int N, M;
    static int[] par;
    static long[] wei;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        while(true) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            if( N ==0 && M==0) break;
            par = new int[N+1];
            wei = new long[N+1];
            for (int i = 1; i <= N; i++) {
                par[i]= i;
            } 
            int a, b, w;
            char cmd;
            for (int i = 0; i < M; i++) {
                st = new StringTokenizer(br.readLine());
                cmd = st.nextToken().charAt(0);
                a = Integer.parseInt(st.nextToken());
                b = Integer.parseInt(st.nextToken());
                if(cmd == '!') {
                    w = Integer.parseInt(st.nextToken());
                    union(a, b, w);
                }
                else {
                    if(find(a) != find(b)) {
                        sb.append("UNKNOWN\n");
                    } else {
                        long diff =  wei[a] - wei[b];
                        sb.append(diff + "\n");
                    }
                }       
            }
        }
        System.out.println(sb);
    }

    public static int find(int n) {
        if (par[n]==n) {
            return n;
        }
        int p = find(par[n]);
        wei[n] += wei[par[n]];
        par[n] = p;
        return p;
    }

    static void union(int a, int b, int w) {
        int pa = find(a);
        int pb = find(b);
        if (pa == pb) return;
        wei[pa] = wei[b] - wei[a] + w;
        par[pa] = pb;
    }
}

 

5719: 거의 최단 경로

import java.io.*;
import java.util.*;
public class Main {
    static final int INF = Integer.MAX_VALUE;
    static final int MAXN = 500;
    static int[] dist;
    static int N, M, S, D;
    static int[][] adj; //adjacent matrix
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        adj = new int[MAXN][MAXN];
        dist = new int[MAXN];
        while(true) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            if(N == 0 || M == 0) return;
            for(int i = 0; i < N; i++) for(int j = 0; j < N; j++) adj[i][j] = 0;
            st = new StringTokenizer(br.readLine());
            S = Integer.parseInt(st.nextToken());
            D = Integer.parseInt(st.nextToken());
            int u, v, p;
            for(int i = 0; i < M; i++) {
                st = new StringTokenizer(br.readLine());
                u = Integer.parseInt(st.nextToken());
                v = Integer.parseInt(st.nextToken());
                p = Integer.parseInt(st.nextToken());
                adj[u][v] = p;
            }
            dijkstra(S);
            removeShortest();
            dijkstra(S);
            if(dist[D] == INF) System.out.println(-1);
            else System.out.println(dist[D]);
        }
    }
    public static void dijkstra(int start) {
        PriorityQueue<Route> pq = new PriorityQueue<>();
        pq.add(new Route(start, 0));
        Arrays.fill(dist, INF);
        dist[start] = 0;
        while(!pq.isEmpty()) {
            Route cur = pq.poll();
            if(dist[cur.v] < cur.weight) continue;
            for(int i = 0; i < N; i++) {
                if(adj[cur.v][i] == 0) continue;
                int next = i;
                int w = cur.weight + adj[cur.v][i];
                if(dist[next] > w) {
                    dist[next] = w;
                    pq.add(new Route(next, w));
                }
            }
        }
    }
    public static void removeShortest() {
        Queue<Integer> q = new LinkedList<>();
        q.add(D);
        while(!q.isEmpty()) {
            int cur = q.poll();
            for(int i = 0; i < N; i++) {
                if(adj[i][cur] != 0 && dist[cur] == dist[i] + adj[i][cur]) {
                    adj[i][cur] = 0;
                    q.add(i);
                }
            }
        }
    }

}
class Route implements Comparable<Route>{
    int v;
    int weight;
    public Route(int v, int weight) {
        this.v = v;
        this.weight = weight;
    }
    @Override
    public int compareTo(Route o) {
        if(this.weight > o.weight) return 1;
        else if(this.weight < o.weight) return -1;
        else return 0;
    }
}

 

17398: 통신망 분할

import java.io.*;
import java.util.*;

public class Main {
    static int N, M, Q, X, Y;
    static long sum;
    static int arrQ[];
    static boolean chk[]; // 처음 넣을 간선인지 아닌지 체크
    static long cnt[];
    static int par[];
    static Edge edges[];

    static int find(int n) {
        if (par[n] == n)    return n;
        return par[n] = find(par[n]);
    }

    static void union(int a, int b) {
        int findA = find(a);
        int findB = find(b);
        if (findA == findB)
            return;
        sum += (1L * cnt[findA] * cnt[findB]);
        cnt[findB] += cnt[findA];
        par[findA] = findB;
    }
    static class Edge {
        int a, b;
        public Edge(int a, int b) {
            this.a = a;
            this.b = b;
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        Q = Integer.parseInt(st.nextToken());
        edges = new Edge[M + 1];
        sum = 0;
        arrQ = new int[Q + 1];
        chk = new boolean[M + 1];
        cnt = new long[N + 1];
        par = new int[N + 1];
        for (int i = 0; i <= N; i++) {
            par[i] = i;
            cnt[i] = 1; // 처음 1로초기화
        }

        for (int m = 1; m <= M; m++) {
            st = new StringTokenizer(br.readLine());
            X = Integer.parseInt(st.nextToken());
            Y = Integer.parseInt(st.nextToken());
            edges[m] = new Edge(X, Y);
        }

        Arrays.fill(chk, true);
        for (int i = 1; i <= Q; i++) { // Q입력
            st = new StringTokenizer(br.readLine());
            int q = Integer.parseInt(st.nextToken()); // arrQ에 1번부터 Q의 정보 입력
            arrQ[i] = q;
            chk[q] = false; //제거 처리
        }

        for (int i = 1; i <= M; i++) {
            if (chk[i] == true) { //마지막까지 제거되지 않은 간선이면 초기 union
                int A = edges[i].a;
                int B = edges[i].b;     
                union(A, B);
            }
        }
        long temp = sum;

        // Q를 마지막부터 꺼내면서 union하고 계산
        for (int i = Q; i >= 1; i--) {
            int N = arrQ[i];
            int A = edges[N].a;
            int B = edges[N].b;
            union(A, B);
        }
        System.out.println(sum - temp);
    }
}