[백준] 12763번 : 지각하면 안 돼

12763번: 지각하면 안 돼

---

[Dijkstra + DFS]

N개의 정점을 탐색하는 것에서 그래프 문제임을 유추할 수 있고, 조건이 주어지며 최소한의 값으로 목표 정점에 도착하는 것을 구하는 것에서 최단경로 문제임을 유추할 수 있다.

 

그저 그런 다익스트라 문제인줄 알고 여유롭게 풀었지만 85% 쯤 오답판정을 받았다. 이럴리가 없는데..하면서 몇 번을 다시 제출했지만 여전히 오답이었다. 틀린 이유에 대한 해답은 질문 게시판에서 찾을 수 있었다.

링크 : https://www.acmicpc.net/board/view/37703#post

 

위의 게시글 작성자분 께서 친절하게 그림과 함께 반례에 대해 설명을 해주셨고, 아차 하며 다시 풀기 시작했다. 이 문제는 택시비(돈)과 시간. 이 두가지 조건을 만족하며 목표 정점까지 '최소값'으로 도달해야하는 문제인 만큼, 우리가 출력해야하는 값(돈)에만 집중하면 오답처리가 된다.

 

일반적으로 다익스트라는 BFS 형태로 풀어왔고, BFS 형태로만 풀 수 있다고 생각했다. (DFS는 도달하는 정점이 항상 최소 경로를 지나지 않음) 하지만 특수한 상황에서는 DFS가 조건들을 만족하며 최소 경로로 도달할 수 있다는 것을 깨달았다.

 

그래서 BFS형태의 다익스트라로만 풀었다가 방법을 추가해 DFS + BFS 형태의 다익스트라로 풀었었다. 여기서 DFS는 NxN개의 boolean 배열을 준비해, 주어진 그래프를 탐색하는데, 목표 정점 N을 도달할 수 있으면 true를 반환하여 거쳐온 정점들에 대해 true를 세팅해주었다. (단, 제한된 택시비와 시간 조건을 만족하는 선에서)

 

말이 조금 어려운데, 예를 들어 목표 정점이 5번이라 했을 때, 1 -> 3 -> 4 -> 5 처럼 5를 도달할 수 있다면

check[1][3] = true

check[3][4] = true

check[4][5] = true로 설정하는 방법이다.

 

이렇게 만들어진 NxN 개의 boolean 배열 check를 가지고 다익스트라에서 탐색할 때

기존엔 limit_money와 limit_time 조건을 만족하는가? 만 체크했다면, 이제는 check[current][next]가 "TRUE"인가? 도 만족하는지 체크하였다.

 

이 방법으로 했을 때 정답은 도출되었으나, 시간 초과를 받았다. 그도 그럴 것이 다익스트라는 O(N^2)의 시간 복잡도를 갖는데, DFS도 같이 수행하므로 시간초과를 받아도 전혀 어색하지 않았다.

---

그래서 방법을 달리하여 DFS에서 다익스트라 알고리즘이 수행하는 로직을 같이 처리하기로 하였다.

# Code </>

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

public class Main {

    static class Edge{
        int tg, time, money;

        public Edge(int tg, int time, int money) {
            this.tg = tg;
            this.time = time;
            this.money = money;
        }
    }

    static final int INF = 1000000000;
    static int n, limitT, limitM;
    static List<Edge>[] list = new ArrayList[101];
    static int[] d = new int[101];

    static boolean DFS(int cur, int time, int money){

        if(cur == n)
            return true;

        boolean result = false;

        for(Edge ne: list[cur]){
            int next = ne.tg;
            int nTime = time + ne.time;
            int nMoney = money + ne.money;

            if(nTime > limitT || nMoney > limitM) continue;

            result |= DFS(next, nTime, nMoney);

            if(result)
                if(d[next] > nMoney)
                    d[next] = nMoney;
        }

        return result;
    }

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

        n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        limitT = Integer.parseInt(st.nextToken());
        limitM = Integer.parseInt(st.nextToken());

        for(int i=1; i<=n; i++){
            list[i] = new ArrayList<>();
            d[i] = INF;
        }

        int l = Integer.parseInt(br.readLine());

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

            int h = Integer.parseInt(st.nextToken());
            int tg = Integer.parseInt(st.nextToken());
            int time = Integer.parseInt(st.nextToken());
            int money = Integer.parseInt(st.nextToken());

            list[h].add(new Edge(tg, time, money));
            list[tg].add(new Edge(h, time, money));
        }
        d[1] = 0;
        DFS(1, 0, 0);

        System.out.println(d[n] == INF? -1:d[n]);
    }
}