[ 소프티어 ] 교차로 (C++)

https://softeer.ai/practice/6256

 

[ 풀이 방법 ]

 

 교차로의 각 위치에 들어온 차들을 저장할 queue와, 차가 들어온 교차로 위치를 저장하는 배열, 차가 들어온 시간을 저장하는 배열, 차가 교차로를 통과한 시간을 저장하는 배열을 차가 들어온 순서대로 생성하고 탐색하여 구현

 

1. 교차로가 모두 빈 경우

  - 아직 탐색되지 않은 첫 번째 차의 도착 시간을 현재 시간으로 초기화한다.

  - 현재 시간에 도착한 차들을 모두 교차로의 올바른 위치에 삽입한다.

  - 오른쪽 교차로가 빈 교차로에 들어온 차들을 교차로 큐에서 빼준 뒤 교차로를 통과한 시간을 저장하는 배열에 현재 시간을 저장한다.

 

2. 교차로 중 일부가 빈 경우

  - 현재 시간을 1초 늘린다.

  - 현재 시간에 도착한 차들을 모두 교차로의 올바른 위치에 삽입한다.

  - 오른쪽 교차로가 빈 교차로에 들어온 차들을 교차로 큐에서 빼준 뒤 교차로를 통과한 시간을 저장하는 배열에 현재 시간을 저장한다.

 

3. 위 과정을 교차로가 모두 찰 때까지 반복한다.

  - 교차로가 모두 찬 경우 아직 교차로를 통과하지 못한 모든 차의 교차로를 통과한 시간을 -1로 초기화하고 반복을 종료한다.

  - 반복이 끝난 뒤, 차가 교차로를 통과한 시간을 저장하는 배열에 저장된 값을 순서대로 출력한다.

 

[ 회고 ]

 오른쪽 교차로가 빈 교차로에 들어온 차들을 교차로 큐에서 빼는 기능을 구현할 때, D -> C -> B -> A 교차로 순으로 동작하도록 구현하였는데, 오른쪽 교차로가 비어있는지 확인한 뒤 교차로를 빠져나가는 과정이 순서대로 진행되기 때문에 오류가 발생했다. AUX 교차로 큐를 만들어 사용함으로써 차가 이미 빠져나간 교차로를 빈 교차로로 확인하는 오류를 해결할 수 있었다.

 

 구현 계획과 검증을 확실하게 하지 않아 오류가 발생한 문제였다. 가장 자주하는 실수인 만큼 실수를 반복하지 않도록 구현 계획과 검증에 시간을 충분히 들여 구현 과정에서 발생하는 오류를 줄이기 위해 노력해야 할 것이다.

 

[ 정답 코드 ]

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

#define A 3
#define B 2
#define C 1
#define D 0

using namespace std;

int N;

vector<int> road;
vector<int> inTime;
vector<int> outTime;

vector<queue<int>> intersec(4);

int curTime = 0;

bool emptyRoad() {
    return intersec[A].empty() && intersec[B].empty() && intersec[C].empty() && intersec[D].empty();
}

bool fullRoad() {
    return !intersec[A].empty() && !intersec[B].empty() && !intersec[C].empty() && !intersec[D].empty();
}

void solve() {

    int idx = 0;
    
    while(true) {
        if(idx >= N && emptyRoad()) return;
        if(emptyRoad()) curTime = inTime[idx];
        else curTime++;

        while(idx < N && curTime == inTime[idx]) {
            intersec[road[idx]].push(idx++);
        }

        if(fullRoad()) {

            return;
        }

        vector<queue<int>> aux(intersec.begin(), intersec.end());
        for(int i = 0; i < 4; i++) {
            if(intersec[i].empty() || !aux[(i+1)%4].empty()) continue;
            outTime[intersec[i].front()] = curTime;
            intersec[i].pop();
        }
        vector<queue<int>>().swap(aux);
    }
}

int main() {

    iostream::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;

    road.resize(N);
    inTime.resize(N);
    outTime.assign(N, -1);
    
    for(int i = 0; i < N; i++) {
        int time; char roadChar;
        cin >> time >> roadChar;

        int roadNum;
        if(roadChar == 'A') roadNum = A;
        if(roadChar == 'B') roadNum = B;
        if(roadChar == 'C') roadNum = C;
        if(roadChar == 'D') roadNum = D;

        road[i] = roadNum;
        inTime[i] = time;
    }
    
    solve();

    for(int i = 0; i < N; i++) {
        cout << outTime[i] << '\n';
    }

    return 0;
}