일방통행 도시 투어의 최대 점수
자바스크립트 코딩테스트 문제로 scc-dag 주제를 연습해보세요. 난이도는 hard이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.
한 방향 도로만 따라 이동할 때, 한 번의 투어로 모을 수 있는 최대 점수를 구하세요.
문제 설명
0번부터 n - 1번까지의 교차로가 있고, 각 교차로에는 한 번만 회수할 수 있는 점수가 놓여 있습니다.
scores[i]는i번 교차로의 점수입니다.roads의 각 원소[a, b]는a번 교차로에서b번 교차로로 가는 일방통행 도로가 있음을 뜻합니다.
당신은 아무 교차로에서나 출발할 수 있고, 도로 방향을 따라 원하는 만큼 이동할 수 있습니다. 같은 교차로를 여러 번 지나갈 수는 있지만, 그 교차로의 점수는 처음 방문할 때만 1번 얻습니다.
이때 한 번의 투어로 얻을 수 있는 최대 총점을 반환하는 maxOneWayTourScore 함수를 작성하세요.
제한사항
1 <= n <= 200000scores.length === n1 <= scores[i] <= 10000000000 <= roads.length <= 300000roads[i] = [a, b]0 <= a, b < n- 같은 방향의 중복 간선이 들어올 수 있습니다.
- 반환값은 가능한 최대 총점입니다.
예시
- 입력:
n = 5,scores = [3, 2, 5, 4, 6],roads = [[0,1],[1,0],[1,2],[2,3],[3,2],[3,4]]→ 출력:20 - 입력:
n = 6,scores = [8, 1, 4, 10, 2, 7],roads = [[0,1],[1,2],[2,0],[2,3],[1,4],[4,5]]→ 출력:23 - 입력:
n = 3,scores = [5, 9, 4],roads = []→ 출력:9
힌트
- 서로 오갈 수 있는 교차로들은 사실상 하나의 큰 묶음처럼 생각할 수 있습니다.
- 그 묶음 안에서는 모든 점수를 다 챙길 수 있습니다.
- 문제는 묶음 사이 이동이 한 방향이라는 점이고, 이 구조를 압축하면 사이클이 없는 그래프가 됩니다.
해설
핵심은 원래 그래프를 그대로 다루지 말고, 강한 연결 요소(SCC, Strongly Connected Component) 단위로 압축하는 것입니다.
1. 왜 SCC로 묶을 수 있을까?
같은 SCC 안의 교차로들은 서로 왕복이 가능합니다. 즉 한 번 그 SCC 안으로 들어가면, 그 안의 모든 교차로를 방문해 점수를 전부 회수한 뒤 원하는 출구 간선을 타고 나올 수 있습니다.
따라서 SCC 하나는 다음 정보만 남기면 됩니다.
- 그 SCC에 속한 교차로 점수의 총합
- 다른 SCC로 나가는 간선들
2. SCC를 압축하면 무엇이 되나?
각 SCC를 하나의 정점으로 바꾸면 사이클이 없는 DAG가 됩니다. 원래 사이클은 모두 SCC 내부로 흡수되었기 때문입니다.
이제 문제는 다음으로 바뀝니다.
각 정점에 점수가 있는 DAG에서, 아무 정점에서 시작해 한 방향으로만 이동할 때 얻을 수 있는 최대 경로 합은?
3. DAG에서는 DP로 최대 점수를 구할 수 있다
압축 DAG의 각 정점 c에 대해:
weight[c]: 그 SCC의 총점dp[c]:c에서 출발했을 때 얻을 수 있는 최대 점수
그러면 점화식은 다음과 같습니다.
dp[c] = weight[c] + max(0, dp[next1], dp[next2], ...)
즉, 현재 SCC 점수는 무조건 먹고, 갈 수 있는 다음 SCC들 중 가장 이득이 큰 경로 하나를 이어 붙이면 됩니다.
이 값은 위상 정렬 순서의 역순으로 계산하거나, DFS 메모이제이션으로 계산할 수 있습니다.
4. 예시 1 보기
scores = [3, 2, 5, 4, 6]
{0, 1}은 서로 왕복 가능, 총점5{2, 3}도 서로 왕복 가능, 총점9{4}의 총점은6
압축 DAG는:
{0,1} -> {2,3} -> {4}
따라서 최대 점수는:
5 + 9 + 6 = 20
5. 시간 복잡도
- SCC 분해:
O(n + m) - 압축 DAG 생성:
O(m) - DAG DP:
O(n + m)
전체 시간 복잡도는 O(n + m)입니다.
대형 입력에서도 충분히 처리할 수 있습니다.
코드 작성
starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.
커스텀 테스트
함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]
실행 결과
아직 실행하지 않았습니다.
댓글
문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.