[C++] 2017 카카오코드 본선 튜브의 소개팅
문제 설명
튜브의 소개팅
얼마 전 소개팅에 실패해 낙담한 튜브를 안타깝게 여긴 친구들은 튜브에게 새로운 사람을 소개해주기로 했다. 좀 더 자연스러운 자리를 만들기 위해, 튜브와 소개팅녀를 파티에 초대하기로 했다.
친구들은 튜브에게 파티에 초대된 모든 사람의 위치를 알려주었다. 사각형 모양의 파티장 입구는 왼쪽 맨 위였고, 만나야 하는 상대의 좌석은 파티장의 오른쪽 맨 아래였다. 파티장의 가로 길이가 n이라고 하고, 세로 길이를 m이라 할 때, 튜브와 소개팅 상대의 위치는 각각, (0, 0), (m - 1, n - 1)이 된다.
튜브는 (0, 0)에서 (m - 1, n - 1)까지 가는 가장 짧은 길을 알고 싶다. 이동은 좌/우/상/하로만 가능하다. 또한, 조금이라도 더 빠르게 이동하고 싶은 튜브는 이동하는 중에 가능한 덜 수다스러운 친구들만 만나고 싶다. 다시 말해, 목표 지점까지 길이가 같은 여러 개의 경로가 존재할 경우, 경로상에 위치한 친구들과 나눠야 하는 대화 시간의 합이 적은 것을 더 선호한다.
튜브에게는 스트레스를 심하게 받을 경우 미친 오리로 변하는 비밀이 있다. 경로 상에 위치한 친구들과 나눠야 하는 대화 시간의 합이 s를 초과한다면 미친 오리로 변하고 소개팅에 실패하고 말 것이다! 그러므로 아무리 짧은 경로라도 친구들과 나눠야 하는 대화 시간의 합이 s를 초과한다면 그 경로를 진행할 수는 없다.
튜브가 소개팅 상대에게 무사히 갈 수 있는 경로를 알려주자.
입력 형식
입력은 파티장의 크기 m과 n 그리고 튜브가 참을 수 있는 대화 시간의 총합 s, 친구와의 대화에 필요한 시간 t가 담긴 2차원 배열 time_map으로 주어진다. t가 -1인 경우는 파티 테이블이 위치한 경우라 지나갈 수 없다. 그리고 시작 지점과 도착 지점에서는 수다에 필요한 시간이 없다, 즉 t = 0이다.
추가 제한조건은 아래와 같다.
- 2 <= n, m <= 50
- 1 <= s <= 2^31-1
- -1 <= t <= 2^31-1
- 모든 입력에는 문제의 조건을 만족하는 경로가 하나 이상 존재한다.
출력 형식
리턴 타입은 원소가 두 개인 정수 배열이다. 튜브가 이동해야 하는 경로의 길이와 해당 경로를 지나갈 때 친구와 나눠야 하는 대화 시간의 총합을 리턴한다.
예제 입출력
mnstime_mapanswer
| 3 | 3 | 150 | [[0, 2, 99], [100, 100, 4], [1, 2, 0]] | [4, 103] |
| 4 | 6 | 25 | [[0, 1, 1, -1, 2, 4], [-1, 7, 2, 1, 5, 7], [-1, 1, -1, 1, 6, 3], [-1, 1, -1, -1, 7, 0]] | [8, 15] |
| 5 | 5 | 12 | [[0, 1, 1, 1, 1], [9, 9, 9, 1, 9], [1, 1, 1, 1, 9], [1, 1, 5, 9, 9], [1, 1, 1, 1, 0]] | [12, 11] |
접근 방법
dp[x좌표][y좌표][목적지로부터 현재지점까지의 거리]로 3차원 dp를 사용하여 해결할 수 있었습니다.
보통 bottom up을 사용한 풀이가 대부분이지만 저는 top-down 성애자여서 top-down방식으로 해결하였습니다.
문제를 해결하기 위해서는 0,0부터 m-1,n-1까지 갈 수 있는 가능한 모든 dist에 대해 검사해 봐야 합니다.
dist의 범위는 m+n-2 ~ m*n정도로 잡을 수 있습니다. 즉 for문을 통해 작은 dist부터 검사하게 되며 이 때 가능한 케이스가 있다면 그 때의 dp값이 정답이 될 것 입니다.
한 케이스(dist)에서는 최소 대화시간을 기준으로 최소가 되는 최적해를 찾아나가면 됩니다.
자세한 설명은 소스코드에 주석처리 하겠습니다.
소스 코드
#include <vector>
#include <algorithm>
#include <iostream>
#include <string.h>
using namespace std;
pair<int, int> direction[4] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
vector<vector<int>> map;
long long dp[50][50][2501];
int M, N, S;
long long MAX = 0x7FFFFFFF;
bool inRange(int x, int y){
return (0 <= x && x < M && 0 <= y && y < N);
}
long long solve(int x, int y, int dist){
long long &ref = dp[x][y][dist];
//목적지에 정상적으로 도착한 경우
if(x == M - 1 && y == N - 1 && dist == 0)
return ref = 0;
if(ref != -1)
return ref;
ref = MAX; //방문 표시
for(int i=0;i<4;i++){
int next_x = x + direction[i].first;
int next_y = y + direction[i].second;
//범위를 벗어나거나, 더 이상 이동할 수 없는 경우, continue
if(!inRange(next_x, next_y) || map[next_x][next_y] == -1 || dist < 1)
continue;
long long ret = solve(next_x, next_y, dist - 1) + map[x][y];
if(ret <= S)
ref = min(ref, ret); //같은 dist일때 대화시간이 짧은 것이 우선순위
}
return ref;
}
// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
vector<int> solution(int m, int n, int s, vector<vector<int>> time_map) {
//전역 변수 초기화
memset(dp, -1, sizeof(dp));
map = time_map;
M = m; N = n; S = s;
int move_distance = MAX;
int sum_of_talk_time = MAX;
//최대한 짧은 거리로 이동하는 것을 구해야 하기 때문에 작은 dist 부터 검사
for(int i= M+N-2; i <= M*N; i++){
long long ret = solve(0,0,i);
//만약 만족하는 해가 존재한다면
if(ret < MAX){
move_distance = i;
sum_of_talk_time = ret;
break;
}
}
vector<int> answer(2);
answer[0] = move_distance;
answer[1] = sum_of_talk_time;
return answer;
}