문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/76504
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
BFS와 DP를 활용하여 푸는 알고리즘 문제였습니다.
현재 있는 도시에 움직이지 않을 경우 z 원씩 쌓을 수 있으므로 z * n원을 얻은 뒤 도로 이동을 통해 잔여 금액인 (query - z * n) 원을 얻는 것이 핵심인 문제였습니다.
알고리즘은 다음과 같습니다.
1. BFS를 통해 [0원, limit원]까지 각각을 만드는 최소 턴 수를 전부 구합니다.
- limit원 이하의 돈을 정확히 만드는 최소 턴 수만 미리 전부 구해둘 경우 큰 금액에 대해서도 `z원 배수를 여러 번 + 잔여 금액` 형태로 쉽게 게산 가능하기 때문
- BFS에서 가능한 이동은 `현재 도시에 있기`, `도로 이동`, 그리고 `순간 이동`
- `순간 이동`의 경우 한 도시에서 다른 모든 도시로 순간 이동하는 케이스를 모두 고려하면 너무 많은 케이스를 고려해야할 수 있으므로 시간 초과가 발생할 수 있음
- 따라서 현재 금액에서 한 번만 몯느 도시에 대해서 순간 이동 처리를 하여 중복 처리를 방지
- visitedTeleport[money] = 현재 BFS 거리 형태로 기록
- BFS가 끝나면, dist[{money, city}] = 최소 턴 수 (방문 못 했을 경우 -1)
- dp[money] = 주어진 도시들의 dist[{money, city}] 중 최솟값
2. 이미 1번에서 dp[money]를 구했으므로 쿼리 c에 대해서는 다음과 같이 처리
- c = k * z + leftover 형태로 정의
- leftover <= limit이고 dp[leftover]가 유효한 값이라면 후보 턴 수 = k + dp[leftover]
- k는 `현재 도시에서 있기`로 채운 턴 수로 여러 k 중 최솟값을 결과로 채택
- 만약 모든 k에 대해 leftover를 만들 수 없을 경우 -1 반환
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <vector> | |
#include <algorithm> | |
#include <queue> | |
#include <climits> | |
using namespace std; | |
const long long INF = LLONG_MAX; | |
const int MAX = 3000 + 30; | |
int N; | |
vector<pair<int,int>> graph[MAX]; | |
// money 범위가 0 ~ limit, city 범위가 0 ~ (N - 1) 이므로 | |
// 인덱스를 "money * N + city" 형태로 치환 | |
int getIdx(int money, int city) | |
{ | |
return money * N + city; | |
} | |
vector<long long> solution(int n, int z, vector<vector<int>> roads, vector<long long> queries) { | |
N = n; | |
for (auto rd : roads) | |
{ | |
int u = rd[0]; | |
int v = rd[1]; | |
int w = rd[2]; | |
graph[u].push_back({v, w}); | |
} | |
int limit = z * z; | |
// dist[(money, city)] = 해당 (money, city) 상태를 달성하는 데 필요한 최소 턴 수 | |
vector<int> dist((limit + 1) * n, -1); | |
// 순간이동 액션 최적화를 위한 배열 | |
// visitedTeleport[m] = "money = m"인 상태에서 | |
// 현재 BFS 층(level)에서 순간이동을 이미 처리했는지 여부 (-1이면 아직, 아니면 그 BFS 층) | |
vector<int> visitedTeleport(limit + 1, -1); | |
queue<pair<int,int>>q; | |
dist[getIdx(0, 0)] = 0; | |
q.push({0, 0}); | |
while (!q.empty()) | |
{ | |
auto [curMoney, curCity] = q.front(); | |
q.pop(); | |
int curDist = dist[getIdx(curMoney, curCity)]; | |
// 1) 가만히 있기: money + z | |
int nxt = curMoney + z; | |
if (nxt <= limit) | |
{ | |
int &dref = dist[getIdx(nxt, curCity)]; | |
if (dref == -1) | |
{ | |
dref = curDist + 1; | |
q.push({nxt, curCity}); | |
} | |
} | |
// 1) 가만히 있기: money + z | |
// 2) 도로 이용: city에서 갈 수 있는 도시(v)로 이동, money + w | |
for (auto edge : graph[curCity]) | |
{ | |
int v = edge.first; | |
int w = edge.second; | |
int nxt = curMoney + w; | |
if (nxt <= limit) | |
{ | |
int &dref = dist[getIdx(nxt, v)]; | |
if (dref == -1) | |
{ | |
dref = curDist + 1; | |
q.push({nxt, v}); | |
} | |
} | |
} | |
// 2) 도로 이용: city에서 갈 수 있는 도시(v)로 이동, money + w | |
// 3) 순간이동: (curMoney, curCity)에서 같은 money로 다른 모든 도시로 이동 | |
// 하지만 매번 모든 도시로 순간이동을 확장하면 너무 비효율적이므로, | |
// "현재 BFS 레벨 curDist에서 money=curMoney인 상태"에 대해 단 한 번만 처리 | |
if (visitedTeleport[curMoney] != curDist) | |
{ | |
// 아직 curDist 레벨에서 순간이동 확장을 안 했다면, 이제 수행 | |
visitedTeleport[curMoney] = curDist; | |
for (int t = 0; t < n; t++) | |
{ | |
if (t == curCity) | |
{ | |
continue; | |
} | |
int &dref = dist[getIdx(curMoney, t)]; | |
if (dref == -1) | |
{ | |
dref = curDist + 1; | |
q.push({curMoney, t}); | |
} | |
} | |
} | |
// 3) 순간이동: (curMoney, curCity)에서 같은 money로 다른 모든 도시로 이동 | |
} | |
// BFS가 끝나면, dp[x] = "정확히 x원을 달성하는 데 필요한 최소 턴" | |
// city는 상관없이 어떤 city에 있어도 되므로, | |
// dist[x, city] 중 최솟값이 dp[x]가 됨 | |
vector<long long> dp(limit + 1, LLONG_MAX); | |
for (int x = 0; x <= limit; x++) | |
{ | |
long long best = LLONG_MAX; | |
for (int c = 0; c < n; c++) | |
{ | |
int dval = dist[getIdx(x,c)]; | |
if (dval >= 0) | |
{ | |
if (best > dval) | |
{ | |
best = dval; | |
} | |
} | |
} | |
if (best < LLONG_MAX) | |
{ | |
dp[x] = best; | |
} | |
} | |
vector<long long> answer; | |
for (long long c : queries) | |
{ | |
// 1. c == 0 인 경우는 이미 0원 상태에서 시작하므로 0턴 | |
if (c == 0) | |
{ | |
answer.push_back(0LL); | |
continue; | |
} | |
// 2. c > 0 인 경우 | |
long long bestAns = -1; | |
long long K = c / z; | |
// k를 K에서 최대 z 정도 줄여보면서 leftover를 dp로 만들 수 있는지 확인 | |
// (여유분 -2는 혹시 모를 경계 효과를 위해 조금 더 잡은 것) | |
long long lowK = max(0LL, K - z - 2); | |
for (long long k = K; k >= lowK; k--) | |
{ | |
long long leftover = c - k * z; | |
if (leftover < 0) | |
{ | |
break; | |
} | |
if (leftover > limit) | |
{ | |
continue; | |
} | |
if (dp[leftover] == LLONG_MAX) | |
{ | |
continue; | |
} | |
// candidate = k(= stay-put 횟수) + dp[leftover] | |
// -> leftover를 만드는 최소턴(dp[leftover]) + 남은 금액은 stay-put(k회) | |
long long cand = k + dp[leftover]; | |
if (bestAns < 0 || cand < bestAns) | |
{ | |
bestAns = cand; | |
} | |
} | |
answer.push_back(bestAns); | |
} | |
return answer; | |
} |

개발환경: Programmers IDE
지적, 조언, 질문 환영합니다! 질문 남겨주세요~
반응형
'알고리즘 > programmers' 카테고리의 다른 글
[Programmers] 동굴 탐험 (0) | 2025.02.04 |
---|---|
[Programmers] 가사 검색 (0) | 2025.02.02 |
[Programmers] 블록 게임 (0) | 2025.01.26 |
[Programmers] 1,2,3 떨어트리기 (0) | 2025.01.24 |
[Programmers] 행렬과 연산 (0) | 2024.11.05 |