알고리즘/programmers

[Programmers] RPG 게임 알고리즘

꾸준함. 2025. 1. 26. 21:35

문제 링크입니다: 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 반환

 

#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;
}
view raw .cpp hosted with ❤ by GitHub

 

개발환경: 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