[SWEA][모의 SW 역량테스트][C++] 2383 점심 식사시간

문제

SWEA 모의 SW 역량테스트 - 2383 점심 식사시간

SW Expert Academy

 

---

문제 풀이

접근 방식

다음 세가지 단계를 통해 문제를 해결하였다.

 

1. 거리 구하기

 

map을 입력 받을 때 1을 입력 받으면 사람이므로 그 위치를 people에 넣어주었고,

1과 0이 아닌 수는 계단을 의미하므로 그때의 위치와 값을 2×3 사이즈인 stair에 넣어주었다.

그 후, 모든 사람들과 2개의 계단들 간의 거리를 구해 distances에 넣어주었다.

 

 

2. 각 사람마다 계단 선택하기 (DFS)

 

사람들은 계단 1 또는 계단2를 선택할 수 있다.

그래서 DFS 방식으로 모든 경우를 탐색하여 각 경우마다의 최소 시간을 구하였다.

 

 

3. 최소 시간 구하기 (solution 함수)

 

위의 단계에서 결정된 계단으로 갈 경우의 거리를 각각 stair1, stair2 벡터에 넣어주고 오름차순으로 정렬한다.

그 후, i - 3 번째의 값이 존재한다면, i-3번째의 값 + 계단의 높이가 i번째 값보다 큰지 확인하고,

더 크다면 i번째 값을 그 값으로 대체해준다. (그 시간이 되어야 i번째 사람이 내려갈 수 있음을 의미한다.)

그렇게 각 벡터 내의 모든 값을 계단 아래로 내려갈 수 있는 시간으로 조정해주었다면,

가장 마지막 값에 계단 높이 + 1을 더한 값이 그 계단으로 내려가는 경우의 최소 시간이 된다.

이렇게 두 계단의 최소 시간을 구하고, 두 값 중 더 큰 값이 이 선택 조합의 최소 시간이 된다.

이렇게 모든 경우를 확인하면 MIN에  최종적인 최소 시간이 저장된다.

 

---

풀이 코드 - C++

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
 
vector<int> choice;
vector<vector<int>> distances;
int MIN;
int stair[2][3];
 
void solution(int n) {
    vector<int> stair1;
    vector<int> stair2;
    for (int i = 0; i < n; i++) {
        if (choice[i] == 0)
            stair1.push_back(distances[0][i]);
        else
            stair2.push_back(distances[1][i]);
    }
 
    sort(stair1.begin(), stair1.end());
    sort(stair2.begin(), stair2.end());
 
    int len1 = stair1.size();
    int len2 = stair2.size();
    for (int i = 0; i < len1; i++) {
        if (i - 3 < 0) continue;
        if (stair1[i] < stair1[i - 3] + stair[0][2])
            stair1[i] = stair1[i - 3] + stair[0][2];
    }
 
    for (int i = 0; i < len2; i++) {
        if (i - 3 < 0) continue;
        if (stair2[i] < stair2[i - 3] + stair[1][2])
            stair2[i] = stair2[i - 3] + stair[1][2];
    }
 
    int result = 0;
    if (len1 != 0)
        result = stair1.back() + stair[0][2] + 1;
    if (len2 != 0 && result < stair2.back() + stair[1][2] + 1)
        result = stair2.back() + stair[1][2] + 1;
 
    if (MIN > result)
        MIN = result;
}
 
void dfs(int n) {
    if (choice.size() == n) {
        solution(n);
        return;
    }
    for (int i = 0; i < 2; i++) {
        choice.push_back(i);
        dfs(n);
        choice.pop_back();
    }
}
 
int main(int argc, char** argv) {
    int test_case;
    int T, N, cnt, n;
    vector<vector<int>> map;
    vector<pair<int, int>> people;
    cin >> T;
    for (test_case = 1; test_case <= T; ++test_case) {
        // 입력 받기
        cin >> N;
        map.assign(N, vector<int>(N));
        distances.assign(2, vector<int>(N));
        people.clear();
        MIN = 987654321;
        cnt = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                cin >> map[i][j];
                if (map[i][j] == 1) {
                    people.push_back({ i,j });
                }
                else if (map[i][j] != 0) {
                    stair[cnt][0] = i;
                    stair[cnt][1] = j;
                    stair[cnt][2] = map[i][j];
                    cnt++;
                }
            }
        }
 
        // 거리 구하기
        n = people.size();
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < n; j++) {
                distances[i][j] = abs(stair[i][0] - people[j].first) + abs(stair[i][1] - people[j].second);
            }
        }
        dfs(n);
 
        cout << "#" << test_case << " " << MIN << "\n";
    }
    return 0;
}

실행 결과