[백준 / BOJ] 2611 자동차 경주

문제

출처 : www.acmicpc.net/problem/2611

2611번: 자동차경주

N개의 지점이 있는 그래프가 주어진다. 각 지점사이를 연결하는 도로에는 그 도로를 지날때 얻는 점수가 있다.

1번지점에서 출발해서 다시 1번지점으로 돌아올때, 가장 많이 얻을수있는 점수와, 그때의 경로를 출력하는 문제다.

도로는 단방향 이다.

풀이

dp배열에 (dp[idx] = idx까지 도착했을때 얻은 최대 점수) 를 저장해준다.

DFS를 돌리며, 

dp[현재 도로에 도착했을때 까지 얻은 점수] + 다음 선택할 도로의 점수 >= dp[다음 도로에 저장된 점수]

을 만족할때만 다음 도로로 넘어가게 해주면된다.

 

그림을 보자

괄호 안에 있는 숫자가 그 지점까지 갔을때 얻은 점수들의 합이다. (dp에 저장되어있는 값이라 생각하면됨)

초기 dp값은 전부 0으로 초기화 되어있으니, 어느 경로로 가던지 dp에 저장되어있는값보다 커진다.

따라서 움직이는 경로는 

1 -> 2 -> 3 -> 1 이 된다. (빨강선)

 

1번에서 갈수있는 남은 지점인 4번을 거쳐서 2번으로 가는경우 더 많은 점수를 얻을수있다.

dp[현재 도로에 도착했을때 까지 얻은 점수] + 다음 선택할 도로의 점수 >= dp[다음 도로에 저장된 점수]

조건이 성립된다.

 

(1 -> 4 -> 2) 가 21로 (1 -> 2) 10보다 큼

dp값을 21로 업데이트하고, 1 -> 2 연결을 4 -> 2 로 바꾼다. 

 

경로는

각 노드의 부모를 저장하고 역순으로 출력해주면된다.

위 경우는

par[1] = 3

par[3] = 2

par[2] = 4

par[4] = 1

이 되고,

역순으로 출력하면,

1 -> 4 -> 2 -> 3 -> 1 이된다.

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/2611%20%EC%9E%90%EB%8F%99%EC%B0%A8%20%EA%B2%BD%EC%A3%BC/main.cpp

devxb/JJUNalgo