[Softeer] 교차로, C++

 

Softeer

문제 요약

자동차별로 교차로를 통과하는 시간 출력하기
우측 도로에 자동차가 없어야 통과할수 있음

접근

1. 머리에 생각나는 대로 알고리즘 작성

1. A~D까지 도로 Queue 생성, 입력에 대해서 도로별로 시간을 push
   1. 출력을 위해 queue도 생성
2. Time(t) = 0 부터 시작해서 매 초 각 도로 확인
   1. A~D 도로의 첫번째 차가 도착한 시간 확인.
   2. 차 시간이 현재 시간보다 작거나 같은 경우 오른쪽에 차가 없으면 체크
   3. 나머지 경우 패스(현재시간보다 크거나, 작거나 같지만 오른쪽에 차가 있는 경우)
   4. 네 도로 모두 확인후 체크된 도로의 아이템 pop
      1. 출력을 위해 새로운 A~D queue에 저장
   5. 특정 시간에 네 도로가 꽉 차있으면 이후 모든 값은 -1로 처리
      1. (출력 a~d queue에 -1로 저장)
3. A~D 도로에 차가 없는 경우 출력 시작

void algorithm()
{
    int t = 0;
    int check[4];
    while (!roads[0].empty() || !roads[1].empty()
             || !roads[2].empty() || roads[3].empty()
    )
    {
        memset(check, 0, sizeof(int) * 4);
        checkRoad(check, t);
        if (isDeadlock(check, t))
        {
            // after all, print -1
            for (int i = 0; i < 4; i++)
            {
            while (!roads[i].empty())
            {
            roads[i].pop();
            tRoads[i].push(-1);
            }
            }
            return; // algorithm break
        }
        // not deadlock
        for (int i = 0; i < 4; i++)
        {
            if (!check[i]) continue;
            if(roads[i].empty()) continue;
            roads[i].pop();
            tRoads[i].push(t);
        }

        t += 1;
    }
}

void checkRoad(int* check, int time)
{
    for (int i = 0; i < 4; i++)
    {
        // 1 check arrival time
        if (roads[i].empty()) continue;
        if (roads[i].front() > time) continue;
        // 2 check right road is empty
        // if top(road[0]), check right(road[3], top's right)
        if (!roads[(i+3)%4].empty() && roads[(i+3)%4].front() <= time) 
            continue;
        check[i] = 1;
    }
}
int isDeadlock(int* check, int time)
{
    int sum = check[0] + check[1] + check[2] + check[3];
    if (sum) return 0; // not deadlock
    for (int i = 0; i < 4; i++)
    {
        // if car is not arrived, not deadlock
        if (roads[i].front() > time) 
            return 0;
    }

    return 1; // deadlock
}

득점 0.0

2. 시간 줄이기 1 - 시간 업데이트

t=0부터 매초 확인하는데 t의 최대값이 10^9로 시간초과가 날수밖에 없었다.
모든 시간을 확인하지 않고 도로의 가장 앞에 있는 차를 기준으로 돌아가게 만들었다.

void algorithm()
{
    int t = findMinTime();
    int check[4];
    while (!roads[0].empty() || !roads[1].empty()
            || !roads[2].empty() || roads[3].empty()
    )
    {
        memset(check, 0, sizeof(int) * 4);
        checkRoad(check, t);

        if (isDeadlock(check, t))
        {
            // after all, print -1
            for (int i = 0; i < 4; i++)
            {
                while (!roads[i].empty())
                {
                roads[i].pop();
                tRoads[i].push(-1);
                }
            }
            return; // algorithm break
        }
        // not deadlock
        for (int i = 0; i < 4; i++)
        {
            if (!check[i]) continue;
            if(roads[i].empty()) continue;
            roads[i].pop();
            tRoads[i].push(t);
        }

        // time update
        int tmp_t = findMinTime();
        if (tmp_t <= t) t += 1;
        else t = tmp_t;
    }
}

그리고 혹시나해서 main에 아래를 추가했다.

ios::sync_with_stdio(false); 
cin.tie(nullptr); 
cout.tie(nullptr);

득점 15.0

3. 시간줄이기 2 - Queue 줄이기

vector<queue<int>> roads(4); // for input 0~3:top-right-bottom-left vector<queue<int>> tRoads(4); // for answer

이런 식으로 queue를 여러개 사용하고, 정답을 저장할때 push, pop을 여러번 사용해서 시간이 오래 걸리는듯 보였다. 메모리가 1024MB이므로 배열을 많이 생성하는 것으로 방향을 잡았다.

득점 15.0

4. 시간줄이기 3 - 시간 업데이트 수정

시간을 업데이트하는 것을 위쪽으로 옮겼고 모든 도로에 있는 값이 현재 값보다 클때 업데이트 하도록 만들었다.
그래도 계속 틀렸는데 모 블로그에 나랑 알고리즘은 같은데 통과한 사람이 다 풀어서 썼길래 나도 풀어서 써봤다.

득점 100.0(통과)

전체 코드

#include <iostream>
#include <queue>
#include <vector>
#include <cstring> // memset
#include <algorithm> // min
using namespace std;

#define MAX_SIZE 200000
#define MAX_TIME 1000000001

int N; // size
int answer[MAX_SIZE];
queue<pair<int, int>> roads[4]; // for input 0~3:top-right-bottom-left

int main()
{
    // 1 init
    cin >> N;
    memset(answer, -1, sizeof(int) * N);
    for (size_t i = 0; i < N; i++)
    {
        int time;
        char road;

        cin >> time >> road;
        roads[road-'A'].push({i, time});
    }

    // 2 algorithm
    int t = min({
        (roads[0].empty()) ? MAX_TIME : roads[0].front().second,
        (roads[1].empty()) ? MAX_TIME : roads[1].front().second,
        (roads[2].empty()) ? MAX_TIME : roads[2].front().second,
        (roads[3].empty()) ? MAX_TIME : roads[3].front().second,
    });

    while (!roads[0].empty() || !roads[1].empty() 
            || !roads[2].empty() || !roads[3].empty()
    )
    {
        // update min time
        int tmp_t[4] = {MAX_TIME, MAX_TIME, MAX_TIME, MAX_TIME};

        for (int i = 0; i < 4; i++)
        {
            if (roads[i].empty()) continue;
            if (roads[i].front().second < tmp_t[i])
                tmp_t[i] = roads[i].front().second;
        }
        if (tmp_t[0] > t && tmp_t[1] > t 
                && tmp_t[2] > t && tmp_t[3] > t
        )
            t = min({tmp_t[0], tmp_t[1], tmp_t[2], tmp_t[3]});

        // checkRoad;
        int check[4] = {0, };
        for (int i = 0; i < 4; i++)
        {
            // 1 check arrival time
            if (roads[i].empty()) continue;
            if (roads[i].front().second > t) continue;
            // 2 check right road is empty
            // if top(road[0]), check right(road[3], top's right)
            int right = (i + 3) % 4;
            if (!roads[right].empty() 
                    && roads[right].front().second <= t
            )
                continue;
            check[i] = 1;
        }

        // deadlock
        if (!check[0] && !check[1] && !check[2] && !check[3])
        {
            break; // algorithm break
        }

        // not deadlock
        for (int i = 0; i < 4; i++)
        {
            if (!check[i]) continue;
            // if(roads[i].empty()) continue;
            answer[roads[i].front().first] = t;
            roads[i].pop();
        }
        t += 1;
    }
    // 3 answer
    for (int i = 0; i < N; i++)
    {
        cout << answer[i] << '\n';
    }

    return 0;
}

새로 알게된 것

1. 맞왜틀? 은 항상 내가 틀린게 맞다.