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

2458: 키 순서

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

public class Main {
    static int N, M, inCnt[], outCnt[];
    static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static ArrayList<Integer> adj[];
    static boolean visited[];

    static int dfs(int curr) {
        int outCnt = 0;
        for (int next : adj[curr]) {
            if (visited[next]) {
                continue;
            }
            inCnt[next]++;
            visited[next] = true;
            outCnt += dfs(next);
        }
        return outCnt + 1;
    }

    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(in.readLine());
        N = Integer.valueOf(st.nextToken());
        M = Integer.valueOf(st.nextToken());
        adj = new ArrayList[N + 1];

        inCnt = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            adj[i] = new ArrayList<>();
        }
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(in.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            adj[u].add(v);
        }
        outCnt = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            visited = new boolean[N + 1];
            outCnt[i] = dfs(i) - 1;
        }
        int answer = 0;
        for (int i = 1; i <= N; i++) {
            if ((inCnt[i] + outCnt[i]) == N - 1) {
                answer++;
            }
        }
        System.out.println(answer);
    }
}

 

 

11266: 단절점

import java.io.*;
import java.util.*;
public class Main {
    static int order[];
    static boolean isCut[];
    static int cnt;
    static ArrayList<Integer> adj[];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        order = new int[N+1];
        isCut = new boolean[N+1];
        adj = new ArrayList[N+1];
        for(int i = 1; i <= N; i++) {
            adj[i] = new ArrayList<Integer>();
        }
        for(int i = 1; i <= M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            adj[a].add(b);
            adj[b].add(a);
        }
        for(int i = 1; i <= N; i++) {
            if(order[i] == 0) {
                dfs(i, true);
            }
        }
        int ans = 0;
        for(int i = 1; i <= N; i++) {
            ans += isCut[i] ? 1 : 0;
        }
        sb.append(ans + "\n");
        for(int i = 1; i <= N; i++) {
            if(isCut[i]) {
                sb.append(i + " ");
            }
        }
        System.out.println(sb);
    }

    private static int dfs(int cur, boolean isRoot) {
        order[cur] = ++cnt;
        int ret = cnt;
        int child = 0;
        for(int next : adj[cur]) {
            if(order[next] == 0) {
                child++;
                int low = dfs(next, false);
                if(!isRoot && low >= order[cur]) {
                    isCut[cur] = true;
                }
                ret = Math.min(ret, low);
            } else {
                ret = Math.min(ret, order[next]);
            }
        }
        if(isRoot && child > 1) {
            isCut[cur] = true;
        }
        return ret;
    }
}

 

11657: 타임머신

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tk = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(tk.nextToken());
        int M = Integer.parseInt(tk.nextToken());

        long[] D = new long[N+1];
        int[][] edgeList = new int[M][3];
        long INF = Long.MAX_VALUE;
        for(int i = 0; i < M; i++) {
            tk = new StringTokenizer(br.readLine());
            edgeList[i][0] = Integer.parseInt(tk.nextToken());
            edgeList[i][1] = Integer.parseInt(tk.nextToken());
            edgeList[i][2] = Integer.parseInt(tk.nextToken());
        }
        Arrays.fill(D, INF);
        D[1] = 0;
        int a, b, w;
        boolean flag = false;
        for(int i = 1; i <= N; i++) {
            for(int j = 0; j < M; j++) {
                a = edgeList[j][0];
                b = edgeList[j][1]; 
                w = edgeList[j][2];
                if(D[a] == INF) continue;
                if(D[b] > D[a] + w) {
                    if(i == N) flag = true;
                    D[b] = D[a] + w;
                }
            }
        }
        StringBuffer sb = new StringBuffer();
        if(flag) sb.append(-1);
        else {
            for(int i = 2; i <= N; i++) {
                sb.append((D[i] == INF ? -1 : D[i]) + "\n");
            }
        }
        System.out.print(sb);

    }
}

 

1753: 최단경로

import java.io.*;
import java.util.*;
public class Main {
    static int N, M, K;
    static ArrayList<int[]> adj[];
    static int dist[];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        K = Integer.parseInt(st.nextToken());
        adj = new ArrayList[N+1];
        dist = new int[N+1];
        for(int i = 1; i <= N; i++) {
            adj[i] = new ArrayList<int[]>();
        }
        for(int i = 1; i <= M; 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});
        }
        dijkstra();
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= N; i++) {
            sb.append(dist[i] == Integer.MAX_VALUE ? "INF" : dist[i]).append("\n");
        }
        System.out.println(sb.toString());
    }

    private static void dijkstra() {
        PriorityQueue<Route> pq = new PriorityQueue<Route>();
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[K] = 0;
        pq.offer(new Route(K, 0));
        while(!pq.isEmpty()) {
            Route curr = pq.poll();
            if(dist[curr.v] < curr.w) continue;
            for(int[] next : adj[curr.v]) {
                if (dist[next[0]] > curr.w + next[1]) {
                    dist[next[0]] = curr.w + next[1];
                    pq.offer(new Route(next[0], dist[next[0]]));
                }
            }
        }
    }
    public static class Route implements Comparable<Route>{
        int v, w;
        public Route(int v, int w) {
            super();
            this.v = v;
            this.w = w;
        }
        @Override
        public int compareTo(Route o) {
            return this.w - o.w;
        }
    }
}

 

1854: K번째 최단경로 찾기

import java.io.*;
import java.util.*;
public class Main {
    static int N, M, K;
    static ArrayList<int[]> adj[];
    static int dist[];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        K = Integer.parseInt(st.nextToken());
        adj = new ArrayList[N+1];
        dist = new int[N+1];
        for(int i = 1; i <= N; i++) {
            adj[i] = new ArrayList<int[]>();
        }
        for(int i = 1; i <= M; 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});
        }
        dijkstra();
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= N; i++) {
            sb.append(dist[i] == Integer.MAX_VALUE ? "INF" : dist[i]).append("\n");
        }
        System.out.println(sb.toString());
    }

    private static void dijkstra() {
        PriorityQueue<Route> pq = new PriorityQueue<Route>();
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[K] = 0;
        pq.offer(new Route(K, 0));
        while(!pq.isEmpty()) {
            Route curr = pq.poll();
            if(dist[curr.v] < curr.w) continue;
            for(int[] next : adj[curr.v]) {
                if (dist[next[0]] > curr.w + next[1]) {
                    dist[next[0]] = curr.w + next[1];
                    pq.offer(new Route(next[0], dist[next[0]]));
                }
            }
        }
    }
    public static class Route implements Comparable<Route>{
        int v, w;
        public Route(int v, int w) {
            super();
            this.v = v;
            this.w = w;
        }
        @Override
        public int compareTo(Route o) {
            return this.w - o.w;
        }
    }
}