[Java] 백준 2611. 자동차경주

📌 문제 링크 - https://www.acmicpc.net/problem/2611

 

 

---

 

 

 

 

 

 

문제

자동차 경주로는 <그림 1>의 예와 같이 표현된다. 화살표는 각 지점을 잇는 도로를 의미하며 모든 도로는 일방통행 도로로 화살표 방향으로만 움직일 수 있다.

자동차 경주의 코스는 1번 지점에서 출발하여 다시 1번 지점으로 되돌아오는 것이다. 단, 중간에는 1번 지점을 지나서는 안 된다. 경주로는 1번 지점을 제외한 어느 지점에서 출발하여도 1번 지점을 지나가지 않고서는 같은 지점으로 돌아올 수 없도록 되어 있다. 또한 1번 지점에서 다른 모든 지점으로 갈 수 있고, 다른 모든 지점에서 1번 지점으로 갈 수 있다.

각 도로에는 <그림 2>의 예와 같이 그 도로를 지날 때 얻는 점수가 있다.

1번 지점에서 출발하여 가장 많은 점수를 얻어 다시 1번 지점으로 돌아오는 팀이 우승을 하게 된다. 가장 많은 점수를 얻어 1번 지점으로 돌아오는 경로를 찾아 그 얻는 점수와 경로를 출력하는 프로그램을 작성하시오.

 

 

입력

첫째 줄에는 지점의 개수 N이 주어진다. 각 지점에는 1부터 N까지의 서로 다른 번호가 부여된다. 둘째 줄에는 도로의 개수 M이 주어진다. 이어 M개의 줄에는 p ,q ,r의 형식으로 도로의 정보가 주어지는데 이는 p번 지점부터 q번 지점으로 갈 수 있는 도로가 있고 그 도로에 부여된 점수가 r이라는 뜻이다. N은 1000이하의 자연수이고, p와 q는 1이상의 N이하의 자연수이며 r은 100이하의 자연수 이다. p와 q는 같지 않다.

 

 

출력

가장 많은 점수를 얻은 경로를 찾아, 첫째 줄에는 그 얻는 점수를 출력하고 둘째 줄에는 그 경로를 출력한다. 경로를 출력할 때는 지나는 지점들의 번호를 사이에 한 칸의 공백을 두어 출력한다. 출력하는 경로는 반드시 1번 지점에서 시작하여 1번 지점으로 끝나야 한다. 만약 같은 점수를 얻는 경로가 둘 이상일 경우 그 중 하나만 출력하면 된다.

 

 

 

 

 

 

---

 

 

풀이

다이나믹 프로그래밍을 활용한 위상 정렬 문제다.

 

        while(M-- > 0) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int score = Integer.parseInt(st.nextToken());

            roadList.get(from).add(new int[] {to, score});
            inDegree[to]++;
        }

입력 받을 때, 양방향이 아닌 일방통행 도로이므로, 단방향으로 도로 정보를 roadList에 저장하며, 도착 지점(to)에 들어오는 간선 개수를 inDegree에 기록한다.

 

 

            for(int[] next : roadList.get(cur)) {
                int node = next[0]; // 다음 지점
                int score = next[1] + maxScore[cur]; // 다음 지점으로 갈 경우 점수

                if(maxScore[node] < score) {
                    maxScore[node] = score;
                    prev[node] = cur;
                }
                if(--inDegree[node] == 0) {
                    q.offer(node);
                }
            }

이후, 시작 지점(1번)을 큐에 넣고 탐색을 시작한다.
현재 지점에서 다음 지점(node)으로 이동했을 때 얻는 점수가 기존의 maxScore[node]보다 크다면, 점수를 갱신하고, 경로 정보(prev[node])도 현재 지점으로 갱신한다.

 

탐색한 간선을 처리하면서, 해당 도착 지점의 진입 차수(inDegree)를 감소시키고, 만약 진입 차수가 0이 되었다면 큐에 추가한다.

 

마지막으로 prev를 활용하여 경로를 추적하여 출력하면 된다.

 

 

---

 

 

코드

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

/*
 https://www.acmicpc.net/problem/2611
 1번 지점에서 출발하여 가장 많은 점수를 얻어 다시 1번 지점으로 돌아오는 팀이 우승
 */
public class Main_2611 {
    private static final int START = 1; // 출발지
    private static int[] maxScore; // 지점 별 최대 점수
    private static int[] inDegree; // 각 지점의 진입 차수
    private static int[] prev; // 이전 지점
    private static List<List<int[]>> roadList; // 길 정보


    public static void main(String[] args) throws IOException {
        init();
        getMaxScore();
        print();
    }//main


    private static void getMaxScore() {
        Queue<Integer> q = new LinkedList<>();
        q.offer(START);

        int cur;
        while(!q.isEmpty()) {
            cur = q.poll();

            // 1번 지점에서 시작하여 1번 지점으로 끝나야 한다
            if(cur == START && inDegree[START] == 0) break;

            for(int[] next : roadList.get(cur)) {
                int node = next[0]; // 다음 지점
                int score = next[1] + maxScore[cur]; // 다음 지점으로 갈 경우 점수

                if(maxScore[node] < score) {
                    maxScore[node] = score;
                    prev[node] = cur;
                }
                if(--inDegree[node] == 0) {
                    q.offer(node);
                }
            }
        }
    }//getMaxScore


    private static void print() {
        StringBuilder ans = new StringBuilder();
        Stack<Integer> path = new Stack<>();
        int cur = START;

        while(true) {
            path.add(cur);
            if(prev[cur] == START) {
                path.add(START);
                break;
            }

            cur = prev[cur];
        }

        // 첫째 줄에는 점수를 출력
        ans.append(maxScore[START]).append('\n');
        // 둘째 줄에는 경로를 출력
        while(!path.isEmpty()) {
            ans.append(path.pop()).append(' ');
        }

        System.out.print(ans);
    }//print


    private static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());

        roadList = new ArrayList<>(N+1);
        maxScore = new int[N+1];
        inDegree = new int[N+1];
        prev = new int[N+1];

        for(int i=0; i<=N; i++) {
            roadList.add(new ArrayList<>());
        }

        StringTokenizer st;
        while(M-- > 0) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int score = Integer.parseInt(st.nextToken());

            roadList.get(from).add(new int[] {to, score});
            inDegree[to]++;
        }

        br.close();
    }//init


}//class