2022-07-20 [7회차] 알고리즘 스터디

1. 파티 - 골드 3

출처 https://www.acmicpc.net/problem/1238

1238번: 파티

 

  Sol) 스터디원 코드

<hide/>
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 문제
 * N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.
 * 어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다.
 * 각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.
 * 이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라.
 *
 * 입력
 * 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다.
 * 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어온다.
 * 시작점과 끝점이 같은 도로는 없으며, 시작점과 한 도시 A에서 다른 도시 B로 가는 도로의 개수는 최대 1개이다.
 * 모든 학생들은 집에서 X에 갈수 있고, X에서 집으로 돌아올 수 있는 데이터만 입력으로 주어진다.
 *
 * 출력
 * 첫 번째 줄에 N명의 학생들 중 오고 가는데 가장 오래 걸리는 학생의 소요시간을 출력한다.
 */
public class Main {

    static class Node {
        int to;
        int cost;

        public Node(int to, int weight) {
            this.to = to;
            this.cost = weight;
        }
    }

    static int N, M, X;
    static int INF = 1000000001;
    static ArrayList<ArrayList<Node>> forward_graph, reverse_graph;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] arr = br.readLine().split(" ");
        N = Integer.parseInt(arr[0]);
        M = Integer.parseInt(arr[1]);
        X = Integer.parseInt(arr[2]);

        // 이 부분이 가장 중요
        // X에서 출발해서 다른 정점으로 forward_graph와
        // 다른 정점에서 X로가는 reverse_grapgh를 따로 사용
        forward_graph = new ArrayList<>();
        reverse_graph = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            forward_graph.add(new ArrayList<>());
            reverse_graph.add(new ArrayList<>());
        }

        /**
         * 4 8 2
         * 1 2 4
         * 1 3 2
         * 1 4 7
         * 2 1 1
         * 2 3 5
         * 3 1 2
         * 3 4 4
         * 4 2 3
         */
        for (int i = 0; i < M; i++) {
            String[] road = br.readLine().split(" ");
            int source = Integer.parseInt(road[0]);
            int arrive = Integer.parseInt(road[1]);
            int cost = Integer.parseInt(road[2]);
            forward_graph.get(source).add(new Node(arrive, cost));
            reverse_graph.get(arrive).add(new Node(source, cost));
        }

        int[] forward_dist = dijkstra(forward_graph);
        int[] reverse_dist = dijkstra(reverse_graph);

        int answer = Integer.MIN_VALUE;
        for (int i = 1; i <= N; i++) {
            answer = Math.max(answer, forward_dist[i] + reverse_dist[i]);
        }

        System.out.println(answer);
    }

    public static int[] dijkstra(ArrayList<ArrayList<Node>> graph) {
        int[] dist = new int[N + 1];
        Arrays.fill(dist, INF);

        // forward_dist와 reverse_dist에서 가장 오래 걸리는 학생의 소요시간을 구할 때
        // X번 마을은 0으로 바꿔줘야 max값에서 제외 됨
        dist[X] = 0;

        boolean[] visited = new boolean[N + 1];

        PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(x -> x.cost));
        pq.offer(new Node(X, 0));

        while (!pq.isEmpty()) {
            Node curNode = pq.poll();
            if (visited[curNode.to]) {
                continue;
            }

            visited[curNode.to] = true;

            for (int i = 0; i < graph.get(curNode.to).size(); i++) {
                Node adjNode = graph.get(curNode.to).get(i);

                if (!visited[adjNode.to]
                        && dist[adjNode.to] > curNode.cost + adjNode.cost) {
                    dist[adjNode.to] = curNode.cost + adjNode.cost;
                    pq.offer(new Node(adjNode.to, dist[adjNode.to]));
                }
            }
        }

        return dist;
    }
}

    - 단방향이라 인접행렬에 연결해줄 필요없다.

    - 최단 경로에서 오래걸리는 학생을 구해준다.

    - 플로이드-워셜과 비슷

    - 그래프를 두 개 만들고 다익스트라 두 번 돌린다.

    -  출발지랑 도착지만 바꿔서 다익스트라에 넣어준다.

    - spfa가 벨만-코드보다 빠르다.

 

 

 

참고 spfa) 음수 가중치가 있는 경우 -> 벨만포드, SPFA 두개로 풀어보기

https://www.acmicpc.net/problem/1865

1865번: 웜홀

 

 

  cf) https://leetcode.com/problems/network-delay-time/discuss/1696725/java-spfa-faster-than-99-4ms-step-by-step-spfa

JAVA - SPFA : Faster than 99% - 4ms (Step by Step SPFA) - LeetCode Discuss

    - 음수 가중치

    - spfa 알고리즘

<hide/>
class Solution {
public int networkDelayTime(int[][] times, int n, int k) {
    int[][] graph = new int[n+1][n+1];
    
    //fill with -1 because weight can be Zero
    for(int[] g : graph) {
        Arrays.fill(g, -1);
    }
    
    //add weights against edges int 2D matrix
    for(int[] t : times) {
        graph[t[0]][t[1]] = t[2];
    }
    
    //this visited array keeps track what is already there in queue(spfa)
    boolean[] visited = new boolean[n+1];
    
    //distance array to maintain the current lowest dist
    int[] dist = new int[n+1];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[k] = 0;
    
    Queue<Integer> spfa = new LinkedList();
    spfa.add(k);
    visited[k] = true;
    while(!spfa.isEmpty()) {
        int curr = spfa.poll();
        
        //AGAIN: when we remove a node, we mark it as unvisited because this just keeps track of what is there in the queue
        visited[curr] = false;
        
        for(int i=1; i<=n; i++) {
            //IMP: Note edge weight can be zero
            if(graph[curr][i] != -1) {
                //if found lesser weight, update
                if(dist[i] > dist[curr] + graph[curr][i]) {
                    dist[i] = dist[curr] + graph[curr][i];
                    
                    //if node is already in queue, don't add again
                    if(!visited[i]) {
                        spfa.add(i);
                        //once added mark it as visited
                        visited[i] = true; 
                    }
                }
            }
        }
    }
    
    //iterate to get result
    int result = 0;
    for(int i=1; i<=n; i++) {
        result = Math.max(dist[i], result);
    }
    
    //confirm that every edge is reachable or not and return result
    return result == Integer.MAX_VALUE ? -1 : result;
}
}

 

 

2.  섬 연결하기 - lv 3

출처 https://school.programmers.co.kr/learn/courses/30/lessons/42861

프로그래머스

 

  MySol)  0.5 ~ 0.7ms

<hide/>
import java.util.Arrays;
public class Test2 {
    static  int [] parents;
    public  static  int solution(int n, int[][] costs) {
        int answer = 0;
        Arrays.sort(costs, (x, y) -> x[2] - y[2]);
        int graph[][] = new int[n][n];
        parents = new int[n];
        int weightSum = 0;

        for(int i = 0; i < n ; ++i){
            parents[i] = i;
        }

        for(int i = 0; i < n; ++i){
            if(find(costs[i][0]) != find(costs[i][1])){ // 연결되지 않은 경우에
                union(costs[i][0], costs[i][1]);
                weightSum += costs[i][2];
            }
        }
        return weightSum;
    }

    public static void union(int a, int b){
        int aP = find(a);
        int bP = find(b);

        if(aP != bP){
            parents[aP] = bP;
        }
    }

    public static  int find(int a){
        if(a == parents[a]){
            return a;
        }
        return parents[a] = find(parents[a]);
    }

    public  static  void main(String[] args){
        int[][] cost = {{0,1,1},{0,2,2},{1,2,5},{1, 3, 1},{2,3,8}};
        System.out.println(solution(4, cost));
    }
}

    - 전형전인 크루스칼 알고리즘 문제이다. 

 

  Sol) 스터디원 코드 

<hide/>
import java.util.*;
class Solution {
    public int solution(int n, int[][] costs) {
        Arrays.sort(costs, (x, y) -> x[2] - y[2]);

        int[] visited = new int[n];

        for (int i = 0; i < n; i++) {
            visited[i] = i;
        }

        int answer = 0;
        for (int[] edge : costs) {
            int parent1 = findParent(edge[0], visited);
            int parent2 = findParent(edge[1], visited);

            if (parent1 == parent2) continue;
            answer += edge[2];
            visited[parent2] = parent1;
        }
        return answer;
    }

    public static int findParent(int edge, int[] visited) {
        if (visited[edge] == edge) return edge;
        return findParent(visited[edge],visited);
    }
}

    - cnt를 넣으면 시간이 많이 줄어든다.

 

 

---

7/ 24 일요일

(프로그래머스 실전 모의고사 1차 테스트로 대체)