[Softeer] S803 교차로

[Softeer]

Question

Language: Python

해당 문제는 보기에는 복잡하지만, 각 교차로 별로 queue을 통해 관리하면 수월하게 문제를 풀이하는 것이 가능하다.

1. 각 구역 별로 차량 정리

sector_transition={
    "A":0,"B":1,"C":2,"D":3
}

#각 구역별로 차량을 정리한다.
for index in range(n):
    time,sector=int(cars[index][0]),cars[index][1]
    sector_waitings[sector_transition[sector]].append((index,time))

1. 현재 시간을 관리하면서, 각 교차로에 대해 현재 시간에 있는 차량을 조사한다.

is_waiting=[0]*4 #각 구열별로 현재 시간대에 대기유무
#각 교차로에 대해 현재 시간에 대기하고 있는 차량이 있는지 조사한다.
for sector in range(4):
    if sector_waitings[sector]:
        index,time=sector_waitings[sector][0]   
        next_time=min(next_time,time)
        if time <= current_time:
            is_waiting[sector]=1

1. 제약 조건에 대한 처리

#현재 교차로에 차량이 없는 경우 --> 새로운 차량을 진입시키기 위해 다음 시간대로 옮긴다.
if sum(is_waiting)==0:
    current_time=next_time
    continue

#교착상태인 경우 멈춘다
if sum(is_waiting)==4:
    break

1. 각 구역별로 차량 처리

for sector in range(4):
    if is_waiting[sector] and not is_waiting[(sector-1)%4]:
        index, _=sector_waitings[sector].popleft()
        passing_times[index]=current_time
        pass_count+=1

Solution

from collections import deque,defaultdict
from functools import reduce
from math import inf
import sys

def solution():
    pass_count=0 #교차로를 통과한 차량의 대수
    passing_times=[-1] * n #각 차량에 대해 교차료를 통과한 시간을 저장하는 배열
    sector_waitings=[deque() for _ in range(4)] #각 구역별 대기차량
    current_time=0
    
    sector_transition={
        "A":0,"B":1,"C":2,"D":3
    }

    #각 구역별로 차량을 정리한다.
    for index in range(n):
        time,sector=int(cars[index][0]),cars[index][1]
        sector_waitings[sector_transition[sector]].append((index,time))

    #모든 차량이 지나갈 때 까지 반복문을 지속한다.
    while pass_count< n:
        next_time=inf
        is_waiting=[0]*4 #각 구열별로 현재 시간대에 대기유무
        #각 교차로에 대해 현재 시간에 대기하고 있는 차량이 있는지 조사한다.
        for sector in range(4):
            if sector_waitings[sector]:
                index,time=sector_waitings[sector][0]   
                next_time=min(next_time,time)
                if time <= current_time:
                    is_waiting[sector]=1

        #현재 교차로에 차량이 없는 경우 --> 새로운 차량을 진입시키기 위해 다음 시간대로 옮긴다.
        if sum(is_waiting)==0:
            current_time=next_time
            continue
        
        #교착상태인 경우 멈춘다
        if sum(is_waiting)==4:
            break

        for sector in range(4):
            if is_waiting[sector] and not is_waiting[(sector-1)%4]:
                index, _=sector_waitings[sector].popleft()
                passing_times[index]=current_time
                pass_count+=1
        current_time+=1
        
    for pass_time in passing_times:
        print(pass_time)


if __name__ == "__main__":
    n=int(sys.stdin.readline())
    cars=[list(sys.stdin.readline().split()) for _ in range(n)]
    solution()