[Programmers] RPG 게임 알고리즘

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/76504

프로그래머스

 

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 반환

 

 

개발환경: Programmers IDE  

 

지적, 조언, 질문 환영합니다! 질문 남겨주세요~