[Softeer] HSAT 3회 기출 - 교차로

문제

<배경>

자율주행차가 아래와 같은 교차로를 통과하는 상황을 생각하여 보자. 이 문제에서 다루는 교차로에서는 우회전이 불가능하기 때문에, 아래 그림과 같은 네 가지 방법으로만 교차로를 통과할 수 있다.

자동차들이 동시에 교차로를 통과하면 충돌할 수 있기 때문에, 효율적인 도로 교통 흐름을 위해서는 자동차끼리의 충돌을 방지할 수 있도록 자동차가 적절히 멈춰 있도록 하되, 너무 오래 멈춰 있지 않도록 소프트웨어를 적절하게 작성해야 한다.

이 문제에서 각 도로의 맨 앞에 있는 자동차는 자신을 기준으로 오른쪽에 위치한 도로에 차량이 있으면 1초 동안 출발하지 않고, 차량이 없으면 즉시 교차로를 통과한다. 정확한 설명을 위해 아래와 같은 상황을 생각하여 보자.

 

1번 차량이 C 위치에, 2번 차량이 B 위치에 있다. 두 차량이 동시에 출발하게 되면 왼쪽 그림과 같이 교차로 위에서 충돌할 우려가 있다.

1번 차량을 기준으로 오른쪽에 있는 도로인 B 위치의 도로에 차량이 있기 때문에, 1번 차량은 1초간 출발하지 않고, 2번 차량은 교차로를 통과한다.

A 위치에 있는 차량의 오른쪽에 있는 도로는 D 위치의 도로이고, B 위치에 있는 차량의 오른쪽에 있는 도로는 A 위치의 도로이고, C 위치에 있는 차량의 오른쪽에 있는 도로는 B 위치의 도로이고, D 위치에 있는 차량의 오른쪽에 있는 도로는 C 위치의 도로이다.

위와 같이 1번 차량이 다른 차량이 지나갈 때까지 대기하는 동안 새로운 차량이 C 위치에 계속 진입할 수 있다. 차선이 하나밖에 없기 때문에, 맨 앞에 있는 차량이 지나가기 전까지는 해당 위치의 차선에 적체된 차량이 계속 늘어날 수 있다. 예를 들어 위의 상황에서 1초 뒤에 3번 차량이 B번 위치에, 4번 차량이 C번 위치에 진입할 경우, 아래와 같이 C번 위치에 1번 차량과 4번 차량이 대기하게 된다.

안전을 위해 각 위치마다 1초에 한 대씩만 교차로를 통과할 수 있다. 위의 그림과 같이 하나의 차선에 1번 차량과 4번 차량이 서 있고 이후에 차량이 새로 진입하지 않는다면, 1초 뒤에 1번 차량이 교차로를 통과하고, 다시 1초 뒤에 (즉 전체적으로 2초 뒤에) 4번 차량이 교차로를 통과할 것이다.

 

A, B, C, D 위치에 동시에 차량이 한 대 이상씩 있다면, 교착 상태에 빠져 어떤 차량도 교차로를 통과할 수 없게 된다.

앞으로 $N$대의 차량이 교차로를 통과하기 위해 A, B, C, D 위치에 진입할 것이다.  $i$번 차량은 $t_i$초 때에 $w_i$위치에 진입하여, 해당 차선에 있는 줄 맨 뒤에 있을 예정이다. 혼선을 방지하기 위해, 같은 시각에 각 위치에 진입할 수 있는 차량은 최대 한 대이다.

매초마다, 모든 차량이 진입한 직후, 각 위치의 맨 앞에 있는 차량은 오른쪽 차선에 차량이 없는지 확인한 뒤, 차량이 없다면 교차로를 통과한다.

각 차량이 교차로를 통과하는 시각이 언제인지 계산하는 프로그램을 작성하라.

 

<입력>

 

<출력>

 

<예시>

위 예시에 대한 그림은 아래와 같다.

---

풀이

시간 범위의 값이 크기 때문에 시간을 1씩 증가시키면 시간초과가 날 수 있다.

따라서 교차로에 아무 차가 없을 때는 시간을 하나씩 증가시키지 말고 바로 다음 차의 시간으로 점프하는 방식을 사용하자.

 

큐 자료구조를 사용하기 위해 아래 코드를 추가했다.

from collections import deque

 

각 자동차에 대해 몇번째 차인지, 들어온 시간이 언제인지, 들어온 방향이 언제인지를 묶어 car라는 리스트에 저장했다.

deque()를 4번 실행해 각 방향에 대한 큐를 만들어주었다.

n = int(input())
car = []
for i in range(1,n+1):
    t,w = input().split()
    car.append([i, int(t), w])

car.append([n+1, 10**9+1, 'A'])
carIdx = 0
ans = [-1] * (n+1)
deq = [deque() for _ in range(4)]
counter = 0

 

기본적으로는 counter를 하나씩 증가시키면서 시뮬레이션한다.

현재 counter시간까지의 모든 차를 큐에 넣고(내부 while문),

이후 if문을 사용해 모든 교차로에 차가 있을 떄, 교차로에 차가 없어 시간을 점프하는 경우를 처리했다.

이런 예외 케이스들을 처리하면 이제 정상적인 동작을 시뮬레이션한다.

자신의 오른쪽에 차가 없으면 해당 차를 통과시킬 수 있으므로, 정답배열 ans에 이때의 시간을 기록한다.

약간 특별한 경우로 마주오는 경우는 두 차가 동시에 통과 가능하기 때문에 이때도 맞은 편 차가 올 수 있는지 추가로 확인하고 처리해준다.

while(counter <= 10**9):
    tempCar = car[carIdx]
    number, time, w = tempCar
    while(time <= counter):
        if w=='A': deq[0].append(tempCar)
        elif w=='B': deq[1].append(tempCar)
        elif w=='C': deq[2].append(tempCar)
        elif w=='D': deq[3].append(tempCar)
        carIdx += 1

        tempCar = car[carIdx]
        number, time, w = tempCar
    #while벗어났다는 것은 time>counter라는 것
    if deq[0] and deq[1] and deq[2] and deq[3]:#모든 교차로 차 있다
        break

    #대기하는 차 없으면 다음 차의 시간으로 점프
    if not deq[0] and not deq[1] and not deq[2] and not deq[3]:
        counter = time
        continue
    
    #자기 번호보다 하나 작은 deque가 비어있으면 내가 갈 수 있다
    for i in range(4):
        if deq[i] and not deq[(i-1)%4]:
            x = deq[i].popleft()
            number,_,_ = x
            ans[number] = counter
            if deq[(i+2)%4] and not deq[(i+1)%4]: #맞은 편이랑 같이 
                x = deq[(i+2)%4].popleft()
                number,_,_ = x
                ans[number] = counter
            break
    counter += 1
for i in range(1,n+1):
    print(ans[i])