[JAVA] 백준16118 달빛 여우

문제 링크

---

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

16118번: 달빛 여우

 

 

접근 및 시도 (생각의 흐름)

---

여우는 기본적인 다익스트라로 풀면 된다고 생각을 했고

늑대는 뭔가 변형된 다익스트라 라고 풀어야 하지 않을까? 라고 문제를 보고 떠올렸다.

그렇다면 이 "변형된 다익스트라" 를 어떤 컨셉으로 구현해야 할까?

 

다익스트라 또는 BFS 등의 문제를 풀때 흔히 사용하는 아래와 같은 Node 클래스에

'fastMode를 추가해주자' 라고 생각을 했다.

그러다가 생각이 더 깊어져서

fast -> slow -> fast 이렇게 속도가 다르니

'특정 노드에 fast로 도착했을 때와 slow하게 도착했을때의 모든 distance 값을 계산해서 저장해야 하겠군!' 이라고 생각했다.

하지만 위의 그림처럼 생각이 정돈되지 못했는지 ㅎㅎ

너무 복잡하게 생각했고 ... 막히기 시작했다.

 

늑대의 경우 분명 dist[] 가 단순하지 않다.

즉 다익스트라의 특성상 distance[노드 인덱스] 에 값을 저장하고 업데이트 해 주는 식인데

아래와 같이 어떤 경로를 어떤 속도로 해당 노드에 도착했는지에 따라

distance 값이 여러개(최소니까 한 쌍)를 갖을 수 있다. 

이건 문제에 대해 고민하면서 분명히 인식했던 부분이다.

아래와 같이 1 -> ~~~ -> 4 에 도달하는데에

distance 최소값이 한 쌍(두 값이) 존재한다.

이 중에서도 최소값을 택해야 되겠지만.

 

여기까지 생각하다가 결국 구글링을 하게 됐는데

2차원 배열로 푼 사람의 글을 본 순간 감이 왔다.

int[] disFox = new int[N+1];
int[][] disWolf = new int[2][N+1];

해당 노드까지의 최소값을 구할 때

2차원 배열로 

0번째에는 해당 노드에 fast하게 도착 했을때의 최소값

1번째에는 해당 노드에 slow하게 도착 했을때의 최소값

을 각기 저장하면 되겠다고 생각했다.

 

PriorityQueue에서 poll() 하여 하나씩 노드를 빼내 방문할 때에는

아래와 같이 선언된 Node의 fastMode를 참고한다. (0 : fast,  1 : slow)

    class Node {
        int index;
        int distance;
        int fastMode;
    }

즉, PriorityQueue에서 now 노드를 빼내고 이 노드를 중심으로

인접 there 노드들에 대해 코드를 수행할 때

now 노드의 fastMode -- there 노드의 fastMode를 반대로 교차시켜주면 된다.

 

사용 알고리즘

---

- 다익스트라 응용

- 2차원 배열로 다익스트라의 결과 값 distance 관리

 

 

풀이

---

    class Node {
        int index;
        int distance;
        int fastMode;
    }

 

 

삽질

 

---

맞았다고 생각했는데 계속 뭘 어딜 고쳐도 시간초과가 발생했다.

그러다 발견한...

입력받을 때 steam을 써서 입력받아서 그런지 계속 시간초과가 발생했었다.

이것 때문에 1시간을 코드를 더 쳐다보고 있어야 했다. -_-;

이렇게 naive하게 생각하고 '되겠지~' 라고 생각하는 습관을 버려야 

좋은 개발자가 될 수 있을 것 같다.

 

<Before>

        for (int i = 0 ; i < M ; i++) {
            String input = reader.readLine();
            String[] split = input.split(" ");
            int[] num = Arrays.stream(split).mapToInt(Integer::parseInt).toArray();
            graph.get(num[0]).add(new Node(num[1], 2 * num[2], 1));
            graph.get(num[1]).add(new Node(num[0], 2 * num[2], 1));
        }

 

<After>

        for (int i = 0 ; i < M ; i++) {
            st = new StringTokenizer(reader.readLine());

            int h = Integer.parseInt(st.nextToken());
            int t = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());

            graph.get(h).add(new Node(t, 2 * w, 1));
            graph.get(t).add(new Node(h, 2 * w, 1));
        }

 

총평

---

기본적인 수준의 알고리즘 문제가 아닌, 응용된 문제의 경우

보통 이런식으로 2차원이나 3차원 배열을 잘 활용해야 풀 수 있는 것 같다.

예를들어

거울설치 문제의 경우

기본적인 BFS로직 + 4개방향 값을 저장해야 하므로 3차원 배열까지 선언했어야 했다.

KCM Travel 문제의 경우에도

기본적인 다익스트라의 distance[] 배열이 아닌

2차원 배열로 distance[][] 를 선언해서 풀었어야 했다.

: distance[노드 인덱스][사용한 비용]

이렇게 계산 결과를 2차원 또는 3차원 배열에 저장해야겠다고 떠올릴 수 있을 정도가 되어야

어려운 PS문제도 해결 가능할 것이다.

 

 

[소스코드]

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    private static int N, M; //나무 그루터기 N, 오솔길의 개수 M
    private final static int INF = Integer.MAX_VALUE;
    private static ArrayList<ArrayList<Node>> graph;
    private static int[] dis;
    private static int[][] disWolf;

    private static int[] parent;

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

        StringTokenizer st = new StringTokenizer(reader.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        dis = new int[N+1];
        disWolf = new int[2][N+1];
        parent = new int[N+1];

        resetGraph();
        for (int i = 0 ; i < M ; i++) {
            st = new StringTokenizer(reader.readLine());

            int h = Integer.parseInt(st.nextToken());
            int t = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            
            graph.get(h).add(new Node(t, 2 * w, 1));
            graph.get(t).add(new Node(h, 2 * w, 1));
        }

        Arrays.fill(dis, INF);
        for (int[] a : disWolf) Arrays.fill(a, INF);

        dijkstraForWolf();
        dijkstraForFox();

        int count = 0;
        for (int i = 1 ; i <= N ; i++) {
            if (dis[i] < Math.min(disWolf[0][i], disWolf[1][i])) count++;
        }
        System.out.println(count);
    }

    private static void dijkstraForWolf() {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        int start = 1;
        pq.add(new Node(start, 0, 1));
        disWolf[1][start] = 0;

        while (!pq.isEmpty()) {
            Node node = pq.poll();
            int now = node.index;
            int nowDistance = node.distance;
            int nowFastMode = node.fastMode;

            if (disWolf[nowFastMode][now] < nowDistance) continue;

            for (int i = 0; i < graph.get(now).size(); i++) {
                Node there = graph.get(now).get(i);
                int thereIndex = there.getIndex();
                int thereFastMode = 1 - nowFastMode; //0 : fast,   1 : slow
                int cost = disWolf[nowFastMode][now] + (thereFastMode == 0 ? there.getDistance() / 2 : there.getDistance() * 2);
                //there까지 빠르게 도착하는 비용을 계산하였으므로 비교할 때에도 distWolf[0][there] 와 비교해준다
                if (cost < disWolf[thereFastMode][thereIndex]) {
                    disWolf[thereFastMode][thereIndex] = cost;
                    pq.add(new Node(thereIndex, cost, thereFastMode));
                }
            }
        }
    }

    private static void dijkstraForFox() {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        int start = 1;
        pq.add(new Node(start, 0, 1));
        dis[start] = 0;

        while (!pq.isEmpty()) {
            Node node = pq.poll();
            int now = node.index;
            int nowDistance = node.distance;

            if (dis[now] < nowDistance) continue;

            for (int i = 0; i < graph.get(now).size(); i++) {
                Node there = graph.get(now).get(i);
                int thereIndex = there.getIndex();
                int cost = dis[now] + there.getDistance();

                if (cost < dis[thereIndex]) {
                    dis[thereIndex] = cost;
                    pq.add(new Node(thereIndex, cost, 1));
                }
            }
        }
    }


    static void resetGraph() {
        if (graph != null) graph.clear();
        graph = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            graph.add(new ArrayList<>());
        }
    }

    static class Node implements Comparable<Node> {
        int index;
        int distance;
        int fastMode;
        Node (int index, int distance, int fastMode) {
            this.index = index;
            this.distance = distance;
            this.fastMode = fastMode;
        }

        public int getIndex() {
            return this.index;
        }
        public int getDistance() {
            return this.distance;
        }
        public int getFastMode() { return this.fastMode; }

        @Override
        public int compareTo(Node o) {
            if (this.distance < o.distance) {//distance가 작은 순
                return -1;
            }
            return 1;
        }
    }
}