백준 2611번 : 자동차경주 (Java)

 문제

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

2611번: 자동차경주

2611 자동차경주

 

 구현 방법

최근 위상 정렬 알고리즘을 밀고 있어 위상 정렬임을 알고 풀었는데 만약 몰랐다면 무슨 알고리즘 사용할지 꽤나 고민을 했을 것 같습니다.

다익스트라랑 비슷한 느낌일 수 있는데 다익스트라는 도달한 노드는 거리값이 확정됩니다.

하지만 자동차경주는 도달해도 그 값이 최대값인지 보장되지 않아 해당 노드까지 도달하는 모든 노드들을 비교해야하므로 위상정렬을 사용해야 합니다.

 

저는 점수의 합을 저장하는 sum 변수와 경로를 저장하는 path 변수를 사용해 Node라는 클래스를 생성하여 활용했습니다.

Node를 배열로 만들어 지점에 도달할 때 마다 해당 지점에 존재하는 최대 점수, 현재 이동하는 경로의 최대 점수를 비교하여 현재 이동하는 경로의 최대 점수가 더 클 경우 점수의 합과 경로를 변경해주었습니다.

 

 구현 코드

package BOJ.Gold;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class B2611_자동차경주 {
	static int N, M, from, to, weight, inDegree[];
	static Node nodeArr[]; // 노드마다 점수가 가장 큰 값과 경로를 저장하기 위한 배열
	static List<List<int[]>> list = new ArrayList<>(); // 도로 정보를 저장하는 리스트
	static Queue<Integer> queue = new LinkedList<>(); // 위상 정렬을 돌리기 위한 큐
	static class Node {
		int sum;
		String path; // 경로 저장할 변수
		public Node(int sum, String path) {
			super();
			this.sum = sum;
			this.path = path;
		}
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		N = Integer.parseInt(br.readLine());
		inDegree = new int[N+1];
		nodeArr = new Node[N+1];
		for (int i=0;i<=N;i++) { // 초기화
			list.add(new ArrayList<>());
			nodeArr[i] = new Node(0, "");
		}
		M = Integer.parseInt(br.readLine());
		for (int i=0;i<M;i++) {
			st = new StringTokenizer(br.readLine());
			from = Integer.parseInt(st.nextToken());
			to = Integer.parseInt(st.nextToken());
			weight = Integer.parseInt(st.nextToken());
			list.get(from).add(new int[] {to, weight}); // 도로 정보 저장
			inDegree[to]++; // 진입 차수 저장
		}
		topology();
		System.out.println(nodeArr[1].sum+"\n"+nodeArr[1].path.substring(1, nodeArr[1].path.length()));
	}
	
	static void topology() {
		queue.offer(1); // 1번 지점에서 출발
		while(!queue.isEmpty()) {
			int now = queue.poll();
			Node nowNode = nodeArr[now];
			nowNode.path = nowNode.path + " " +now; // 경로 저장
			if (nodeArr[1].sum != 0 && now == 1) return;
			
			for (int[] next : list.get(now)) {
				// 해당 노드의 경로 점수보다 현재까지의 경로 점수 + 다음 경로 점수가 더 클 때 
				if (nodeArr[next[0]].sum < nowNode.sum + next[1]) {
					nodeArr[next[0]].sum = nowNode.sum + next[1]; // 점수 변경
					nodeArr[next[0]].path = nowNode.path; // 경로 변경
				}
				if (--inDegree[next[0]] == 0) queue.offer(next[0]); // 진입 차수가 0이면 다음 도로
			} 
		}
	}
}

 

정답!