[알고리즘] 택시 (백준 1649번)

1649번: 택시

 아마 내가 자력으로 푼 첫 플래티넘 문제일 듯 하다. 이 문제를 굳이 찾아 풀어 본 건 저번 코딩테스트 중 이런 비슷한 유형의 문제가 나왔어서 한 번 풀어봤다.

 그리고 이 문제 좀 황당한게  마지막 줄에는 공백을 구분으로 C1, C2, …, Ck가 차례대로 주어진다. 이 문장을 보고 난 당연히

 1 3 5 4 ....

이런 식으로 인풋을 주는 건줄 알았는데

1

3

5

4

..

 이렇게 줄로 띄워서 인풋이 들어와서 처음에 런타임 에러가 나는데 원인을 못 찾아서 한참 헤멨다.... 아무리봐도 문장이 잘못됐다.

 

Solution

 문제에서 찾을 수 있는 조건 두 가지가 있다.

1. 사이클이 없는 유향 그래프. (되돌아 올 수 없다.)
2. 경로 수를 구하라

이 두가지로 유추할 수 있는 것은 위상정렬 + DP를 사용하라는 거다. 다만 input으로 주어지는 모든 교차로 번호를 지나와야 한다는 점에서 그걸 어떻게 해결할 지가 관건이다.

 

 핵심은 현재 노드까지 올 때까지의 지나올 수 있는 모든 교차로 개수를 보관하고, 그 교차로들을 지나오는 경로 개수를 함께 보관하는 것이다. 무조건 그 노드까지 지나온 교차로의 개수가 커야지 최적해 되기 때문에 지나온 최대 교차로 개수를 계속 갱신해주는 것이 포인트다.

1.  count[N+1][2] 배열을 만든다.
   1. count[i][0] : i까지 올 때까지 지나온 교차로의 최대 개수 (i 포함)
   2. count[i][1] : count[i][0] 개의 교차로를 지나올 때의 경로 수
2. count[start][1] 에는 기본 경로 개수 1을 저장한다.
3. 위상정렬을 해나간다.
   1. now와 연결된 노드의 count[to][0]이 count[now][0]과 같다면 to까지 올 때의 최대 교차로 개수가 같으므로 경로만 더해준다.
   2. 하지만 count[now][0]이 count[to][0]이 더 크면 지나올 수 있는 최대 교차로 개수를 갱신해주고 경로 개수도 바꿔준다.
4. count[end][0]이 K개와 같으면 모든 교차로를 지나온 것이므로 count[end][1]을 출력한다.
5. count[end][0]이 K개보다 적으면 모든 교차를 지나올 수 있는 경우가 없으므로 0을 출력한다.

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.*

import kotlin.collections.ArrayList

import kotlin.collections.HashMap
import kotlin.collections.HashSet
import kotlin.math.max

import kotlin.math.min

var br = BufferedReader(InputStreamReader(System.`in`))
var bw = BufferedWriter(OutputStreamWriter(System.out))


fun solution() {

    var strtok = StringTokenizer(br.readLine())

    var N = strtok.nextToken().toInt()//정점
    var M = strtok.nextToken().toInt()//간선

    var graph = ArrayList<ArrayList<Int>>()

    for(i in 0..N)
        graph.add(ArrayList())

    var inEdge = Array(N + 1, {0})

    for(i in 0 until M)
    {
        strtok = StringTokenizer(br.readLine())
        var from = strtok.nextToken().toInt()
        var to = strtok.nextToken().toInt()

        graph.get(from).add(to)
        inEdge[to]++
    }

    strtok = StringTokenizer(br.readLine())
    var start = strtok.nextToken().toInt()
    var end = strtok.nextToken().toInt()
    var K = strtok.nextToken().toInt()

    //교차로 집합
    var mid_set = HashSet<Int>()

    for(i in 0 until K)
        mid_set.add(br.readLine().toInt())

    var count = Array(N + 1, {Array(2, {0})})//0 : 방문한 교차로 수, 1 : 교차로를 거친 경로 수

    var queue : Queue<Int> = LinkedList()

    for(i in 1 .. N)
    {
        if(inEdge[i] == 0)
            queue.offer(i)
    }
    count[start][1] = 1

    while(!queue.isEmpty())
    {
        var now = queue.poll()

        //교차로
        if(mid_set.contains(now))
            count[now][0] ++

        if(now == end)
            break

        for(i in 0 until graph.get(now).size)
        {
            var to = graph.get(now).get(i)

            inEdge[to]--

            //크다면 교체
            if(count[now][0] > count[to][0])
            {
                count[to][0] = count[now][0]
                count[to][1] = count[now][1]
            }
            else if(count[now][0] == count[to][0])
                count[to][1] += count[now][1]

            if(inEdge[to] == 0)
                queue.offer(to)
        }
    }

    if(count[end][0] == K)
        bw.write(count[end][1].toString())
    else
        bw.write("0")
}

fun main() {
    solution()


    br.close()
    bw.close()
}