백준 - 파티

문제 링크 ▶︎ 파티

문제 파악

이 문제에서는 도로가 단방향으로 이루어져있어서 x에서 가는 도로와 x로 들어오는 도로를 따로 구해야 x도시를 왕복하는 cost를 구할 수 있다.
즉 각 도시에서 x 도시로 가는 최소 비용과 x 도시에서 각 도시로 가는 최소 비용을 모두 구해서 각 도시별로 더해주면 된다. 최소 비용을 구하는 과정은 그냥 우선순위큐에 cost가 낮은 순으로 받아서 처리하면 된다.

접근 방법

1. a->b로 가는 cost를 저장하는 edges1과 반대로 돌아가는 길을 구하기 위한 b->a로 가는 cost를 저장하는 edges2를 모두 선언한다. 즉, 문제에서 주어지는 길과 그 길의 역방향 길을 모두 저장해 왕복 cost를 구한다.

2. find 함수에서는 cost가 낮은 순으로 저장되는 우선순위큐와 각 도시까지의 비용을 저장하는 visited 배열을 선언한다. 그리고 x에서 시작하기 때문에 visted[x]는 0으로 세팅해서 다시 방문할 수 없게 만든다. 큐에 x,0을 넣고 시작한다.

3. 큐에서 현재 노드와 현재 노드까지 오는데 쓰인 비용을 to, cost로 저장한다. 만약 해당 노드까지 오는 데 쓰인 비용 cost가 이미 그전에 visited[to]에 저장된 cost보다 크다면 또 방문할 의미가 없기 때문에 continue해준다.

4. 다음 노드에서 뻗어나가는 노드를 순회하면서 cost를 더 줄일 수 있다면 큐에 넣어주고 visited를 수정해준다.

5. 최종적으로 visited 배열을 리턴해주고 edges1, edges2를 매개변수로 넣어 함수를 수행하면 각 도시에서 x로 가는 최소비용에 대한 배열, x에서 각 도시로 가는 최소비용에 대한 배열이 나온다.

코드 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int n, m, x, cnt, answer;
    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());
        x = Integer.parseInt(st.nextToken());
        Map<Integer, List<int[]>> edges1 = new HashMap<>();
        Map<Integer, List<int[]>> edges2 = new HashMap<>();
        for (int i = 1; i <= n; i++) {
            edges1.put(i, new ArrayList<>());
            edges2.put(i, new ArrayList<>());
        }
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            edges1.get(a).add(new int[]{b, c});
            edges2.get(b).add(new int[]{a, c});
        }

        int[] a = find(edges1);
        int[] b = find(edges2);
        for (int i = 1; i <= n; i++) {
            if (i == x) continue;
            answer = Math.max(answer, a[i] + b[i]);
        }
        System.out.println(answer);
    }
    public static int[] find (Map<Integer, List<int[]>> edges) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> a[1] - b[1]);
        int[] visited = new int[n + 1];
        Arrays.fill(visited, Integer.MAX_VALUE);
        visited[x] = 0;
        pq.add(new int[]{x, 0});

        while (!pq.isEmpty()) {
            int[] now = pq.remove();
            int to = now[0];
            int cost = now[1];

            if (visited[to] < cost) {
                continue;
            }

            for (int[] next : edges.get(to)) {
                if (visited[next[0]] > cost + next[1]) {
                    visited[next[0]] = cost + next[1];
                    pq.add(new int[] {next[0], next[1] + cost});
                }
            }
        }
        return visited;
    }
}

개선 사항