[소프티어] 교차로

교차로 문제가 너무 긴 관계로 링크로 대체한다.

간단하게 얘기하면 A,B,C,D 교차로가 존재하고

각 교차로에서 오른쪽 방향 교차로에 차가 존재하면 가지 못하고, 아니면 통과할 수 있다.

---

구현문제다.
즉, 알고리즘에 구애받지 않고 주어진 조건에 맞게 차례차례 구현하면 된다.

메모리 제한이 1024MB로, 각 교차로마다 대기열로 Queue를 4개 사용했다.

핵심은 A,B,C,D -> 0,1,2,3 으로 인덱스 번호로 지정해서 Queue<>[] 처럼 큐의 배열로 지정할 수 있다. 여기서 (i+3)%4 mod 연산을 통해 쉽게 오른쪽 교차로를 가르킬 수 있다.

또 다른 핵심은 시간에 대한 제한이 0 <= t <=1_000_000_000 이기 때문에 무작정 while 문을 돌려버리면 시간초과가 난다.
그렇기 때문에 교차로에 차가 존재하지 않으면 대기하는 차의 최소시간으로 업데이트해줘야한다.

머리를 쥐어싸매다가 결국 풀이를 찾아봤지만, 막상 주어진 대로만 구현하면 되는 문제였다.

내 문제는 구현문제를 풀때 너무 주어진대로만 직관적으로 해결하려고 해서 막히는 것 같다. 좀 더 프로그래밍적인 생각을 거친 이후에 접근해야겠다.

코드

import java.io.*;
import java.util.*;

/*
시간 : 3초
메모리 : 1024MB
---
  A
D   B
  C
- 맨 앞에 자동차는 자신 기준 오른쪽 도로의 차량이 있으면 1초 대기, 없다면 즉시 통과
- 1초에 한 대씩만 교차로 통과 가능
- A,B,C,D 에 한대 이상씩 있다면 교착상태에 빠짐

구현문제

반복 방법 : 처음 값을 기준으로 시간 설정하고, +1씩 증가. (만약 0초에 한번 10억초에 한번 들어오면 10억번 증가연산?)
    그렇기에 중간에 차가 들어오지 않는 부분은 패스해야함. (어떻게?)
    교차로에 아무도 없지만, 대기열에는 남아있는 경우 대기열에 가장 최근값으로 시간을 업데이트하고, 계속 진행
    처음에 각 위치의 idx또한 저장. (결과 출력을 위해)
    
교차로 구현 : 메모리가 충분하기에 4개의 교차로를 Queue 자료구조로 구현.

반복 종료조건 : 4개의 교차로 Queue가 모두 비었을 때

시뮬레이션 : 
    - 4개의 대기열에서 꺼낼 수 있는 지 확인
        - 아무것도 교차로에 올 수 없다면 대기열의 가장 최근 값으로 시간을 업데이트
        - 4차가 모두 올 수 있다면 교착상태
        - 두개의 경우가 다 아니라면 
            - 각 교차로에 대해서 오른쪽 교차로에 차가 있는지 확인하고, 없으면 현재 시간으로 결과 배열에 추가
            - 현재 시간 증가

교차로 A,B,C,D 를 int로 표현
(i+3) % 4
즉, mod 연산으로 구분
A = 0
B = 1
C = 2
D = 3

0 A, B, C -> A
1 B, C -> B
2 C, C, D -> C
3 C, D -> C
4 B, D -> B, D

---
2 <= N <= 200_000
0 <= t <=1_000_000_000

*/

class Car {
    int idx; // 결과 배열에 넣기위한 인덱스값
    int time;
    public Car (int i, int t) {
        this.idx = i;
        this.time = t;
    }
}

public class Main {
    public static Queue<Car>[] q = new Queue[4];

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        int N = Integer.parseInt(br.readLine());

        for (int i = 0; i < 4; i++){ // 초기화
            q[i] = new LinkedList();
        }
        
        for (int i=0; i<N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int t = Integer.parseInt(st.nextToken());
            int w = st.nextToken().charAt(0) - 'A';
            q[w].add(new Car(i, t)); // w번 교차로 Queue에 index와 진입시간을 저장
        }

        int[] result = new int[N];
        Arrays.fill(result, -1); // 교착상태를 위한 -1로 결과 배열 초기화
            
        int currentTime = -1;
        while (true) {
            // 모두 비었다면 종료
            if (q[0].isEmpty() && q[1].isEmpty() && q[2].isEmpty() && q[3].isEmpty()) break;
            
            int[] state = new int[4]; // 각 교차로 큐에서 꺼낼 수 있는지 상태를 확인하는 배열
            int minTime = Integer.MAX_VALUE;
            for (int i=0; i<4; i++) {
                if (!q[i].isEmpty()) {
                    int t = q[i].peek().time;
                    minTime = Math.min(t, minTime);
                    if (t <= currentTime) { // 현재 교차로에 들어갈 수 있는 시간인지 체크
                        state[i] = 1;
                    }
                }
            }

            int count = 0; 
            for (int value : state) { // 현재 교차로에 있는 차의 개수
                count += value;
            }

            if (count == 0) { // 교차로에 아무도 진입하지 않음
                currentTime = minTime; // 현재 시간 업데이트
            } else if (count == 4) { // 교착 상태
                break;
            } else { // 교차로 작업
                for (int i=0; i<4; i++) {
                    if (state[i] == 1 && state[(i+3)%4] == 0) {
                        result[q[i].poll().idx] = currentTime;
                    }
                }
                currentTime++;
            }
        }
        
        for (int n : result) {
            sb.append(n).append("\n");
        }
        System.out.print(sb);
    }
    
}