[소프티어] 교차로 / C++ 해설

더 많은 문제풀이는 아래 Github 주소에서 확인하실 수 있습니다.

https://github.com/Dongha-k/softeer-code

GitHub - Dongha-k/softeer-code: softeer 문제 풀이입니다.

문제 출처: https://softeer.ai/practice/info.do?idx=1&eid=803 

Softeer

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
typedef pair<int, int> P;
int main(int argc, char** argv)
{	
	int n;
	int cur = 1000000001;
	vector<P> v[4];
	queue<P> q[4];
	
	cin >> n;
	
	vector<int> result(n, -1);
	for(int i = 0 ; i < n ; i ++){
		int t;
		char load;
		cin >> t >> load;
		cur = min(cur, t);
		q[load-'A'].push({t, i});
	}
	

	while(n){
		bool possible[4];
		bool canGo[4];
		int cnt0 = 4;
		for(int i = 0 ; i < 4 ; i ++) {
			if(!q[i].empty() and q[i].front().first <= cur) possible[i] = true; // 출발할 준비가 되어있는 차가 있음
			else {
				possible[i] = false;
				cnt0 --;
			}
		}
		if(cnt0 == 0){
			cur = 1000000001;
			for(int i = 0 ; i < 4 ; i ++){
				if(!q[i].empty()) cur = min(cur, q[i].front().first);
			}
			continue;
		}
		
		
		int cnt = 4;
		for(int i = 0 ; i < 4 ; i ++){
			if(!possible[i]) {
				canGo[i] = false;
				cnt --;
			}
			else{
				if(possible[(i + 3) % 4]) { // 오른쪽 차도 갈 수 있을 때
					canGo[i] = false;
					cnt --;
				}
				else{
					canGo[i] = true;
					int t = q[i].front().first;
					cur = max(cur, t);
				}
			}
		}

		
		for(int i = 0 ; i < 4 ; i ++){
			if(canGo[i]){
				int idx = q[i].front().second;
				result[idx] = cur;

				q[i].pop();
				n--;
			}
		}

		if(cnt == 0) break; // dead lock
		else cur ++;
	}
	
	for(auto x : result) cout << x << '\n';	

	return 0;
}

 

풀이

 

이 코드의 각각의 데이터의 목적을 알게되면 이해가 더 쉬울 것이라고 생각한다.

queue<P> q[4]: 교차로 별로 큐를 두어 총 4개의 큐가 존재하고 교차로 별로 도착하는 차별로 순서대로 큐를 삽입했다. 큐의 내용은 교차로 도착 시각과 사용자 입력에서 받았던 순서이다.(순서를 저장한 이유는 나중에 순서대로 교차로를 지나는 시각을 다시 출력해야하기 때문에)

 

bool possible[4]: 교차로 별로 이번 시각에 오른쪽 차량 신경안쓰고 갈 수 있는 차가 있는지 먼저 저장한다. 두 가지 상황을 생각할 수 있다.

 - possible 배열이 전부 다 false일 때(cnt0 == 0일 때): 이때는 시간을 기다리게되면 교차로에 도착하는 차가 무조건 존재하기 때문에 가장 가까운 시각을 큐 네개의 front를 탐색하여 cur에 대입한다.(cur은 현재 시각이라고 봐도 괜찮음)

 - 전부다 false가 아닐 때, possible[i]가 true라고 해서 바로 교차로를 지나갈 수 있는 것이 아니다. 오른쪽 차량도 possible[(i + 3) % 4]가 true이면 지나가지 못하기 때문이다. 그렇기 때문에 한번의 검증을 더 거쳐야한다.

 

bool canGo[4]: 최종적으로 지나갈 수 있는 차량을 저장한다.

 - 전부다 false일 때(cnt == 0): 교차로 위에 차량이 있음에도 못지나간다는 것은 deadlock 상태가 된다. 이 상태에서 차량이 뒤에 계속 와도 계속 정지해있으므로 break한다.

 - 전부다 false가 아닐 때 canGo[i]가 true인 i번째 교차로 큐의 front를 이동시킬 수 있다.

현재 시각 cur 의 경우 이번에 빠져나가는 차량 중 가장 늦게 교차로에 도착한 차량의 시각이 동시에 차량이 교차로를 통과하는 시각과 같다. 교차로 이동은 1초가 걸리므로 이번 시각에 Deadlock 상태가 아니였다면 한 차량은 이번에 교차로를 통과했다는 말과 같다. 그러므로 1초를 더해주는 작업을 한다.

 

 

vector<int> result(n, -1): 최종적으로 교차로를 통과한 시각을 저장한다. 값이 위에서 update 안되고 -1로 계속 저장되어 있는 차량의 번호는 이전에 Deadlock이 발생하여 반복문을 빠져나온 경우이다.

 

 

주의해야할 점: 시간복잡도 문제

t는 1억까지 올 수 있기 때문에 시간에 대해서 반복문을 돌게되면 시간초과가 난다. 그렇기 때문에 큐를 나누어 구성해서 front만 조건에 맞게 pop 해주면 좋을 것 같다.

 

A 10
B 10
A 100000

입력과 같이 한 참뒤에 혼자 들어오는 차량의 경우도 테스트 케이스로 생각해보면 좋을 것 같다.