[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;
}