[C++] SWEA 4408 - 자기 방으로 돌아가기

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWNcJ2sapZMDFAV8&categoryId=AWNcJ2sapZMDFAV8&categoryType=CODE

SW Expert Academy

<풀이>

1. 학생들의 현재 방과 돌아가야할 방 번호들을 입력받는다.

2. 학생들이 모두 이동하는데 걸리는 최소 시간을 출력한다.

 

<해법>

1. 최소 이동시간의 경우 이해하기

=> 가장먼저, 이동시간이 최소가 되는 경우가 언제인지 생각해 보아야합니다.

곰곰히 생각해보면, 한번에 학생들을 많이 움직여야 합니다. 그러기 위해서는 앞 번호 방부터 복도가 겹치지 않게해서 학생들을 많이 움직이게 해야합니다.

따라서, 저는 학생들의 방 정보를 현재 방 번호 크기 기준으로 정렬하였습니다.

 

2. 최소 이동시간 구하기

=> 정렬한 방 정보를 이용하여, 복도가 겹치지 않게 이동할 학생들을 정합니다. 이 때, 사용되는 복도를 유의해야합니다. 이 문제는 복도를 중앙에 두고 위, 아래로 방이 있습니다.

이 말은, 1 -> 3 방으로 가는 학생과 4 -> 6 방으로 가는 학생의 복도가 겹친다는 뜻 입니다.

따라서, 단순히 사용되는 복도를 설정할 때, 방의 숫자로만 하시면 안됩니다.

저는 위와 같은 경우를 해결하기 위해서, 1 -> 3 방으로 가는 학생을 1 -> 4 방으로 가는 학생처럼 생각하여서 문제를 풀었습니다.

 

#include <iostream>
#include <string.h>
#include <vector>
#include <algorithm>
 
using namespace std;
 
//구조체 : 방 정보
struct room {
    //시작 방 번호, 도착 방 번호
    int start, finish;
};
 
int N;
vector<room> v;
bool visited[400];
int answer;
 
//정렬 기준(시작 방 번호에 따라 정렬)
bool compare(room r1, room r2) {
    if (r1.start == r2.start) {
        return r1.finish < r2.finish;
    }
    return r1.start < r2.start;
}
 
bool allStudentReturn() {
    for (int i = 0; i < N; i++) {
        if (!visited[i]) {
            return false;
        }
    }
    return true;
}
 
int main() {
 
    int test_case;
    int T;
 
    cin >> T;
 
    for (test_case = 1; test_case <= T; test_case++) {
 
        //초기화
        N = 0;
        v.clear();
        memset(visited, false, sizeof(visited));
        answer = 0;
 
        //입력
        cin >> N;
        for (int i = 0; i < N; i++) {
 
            int room1, room2;
            cin >> room1 >> room2;
 
            //작은 번호 방에서 큰 번호 방으로 출발하도록 설정
            if (room1 > room2) {
                v.push_back({ room2, room1 });
            }
            else {
                v.push_back({ room1, room2 });
            }
        }
 
        //정렬(시작 방 번호가 작은 순서대로)
        sort(v.begin(), v.end(), compare);
 
        //시간 계산
        while (true) {
 
            //모든 학생이 방으로 돌아간 경우 -> 종료
            if (allStudentReturn()) {
                break;
            }
 
            int finish = 0;
 
            //모든 학생 점검
            for (int i = 0; i < N; i++) {
 
                //아직 방을 이동하지 못하였고 && 복도가 겹치지 않을 경우 -> 동시에 움직일 수 있음
                if (!visited[i] && v[i].start > finish) {
 
                    //방문 처리
                    visited[i] = true;
 
                    //방이 홀수인 경우 -> 쓰는 복도는 결국 방 번호가 짝수인 경우와 같다
                    if (v[i].finish % 2 == 1) {
                        finish = v[i].finish + 1;
                    }
                    else {
                        finish = v[i].finish;
                    }
                }
            }
 
            //시간 + 1
            answer++;
        }
 
        //결과 출력
        cout << "#" << test_case << " " << answer << "\n";
    }
 
    //종료
    return 0;
}

 

그리디 알고리즘과 구현에 대해 알아볼 수 있는 문제였습니다.