[인증평가(3차) 기출] 교차로 - lv3

문제

Softeer

Softeer

풀이

N만큼 반복문을 돌며 교차로에 새로 들어서는 차량의 도착 시간 및 방향을 입력받아 입력된 차량들이 교차로를 지나간 시간이 어떻게 되는지 출력하는 문제이다. 따라서 시간의 흐름에 따라 교통상황이 어떻게 흘러가는지 면밀하게 살펴 문제에 접근할 필요가 있다.

시간의 흐름을 구현하는것이 핵심이며, 새로 차량 정보가 입력되면 그 이전 시점까지의 교통 상황을 정리하면 된다. 1초 동안, 만약 차량들이 서로 마주보고 있다면 동시에 지나갈수 있고 그렇지 않다면 오직 하나의 차량만 지나갈 수 있다. 새로운 차량이 들어올 땐 교착상황에 유의해야하며, 교착상황이 발생하면 그 이후에 들어온 차량들은 영원히 교차로를 빠져나가지 못한다.

그 외에 도로는 들어온 순서대로 차량이 빠져나가므로 큐로 구현하면 된다.

문제 상황을 잘 살펴 프로세스를 따져보는것이 무엇보다 중요한 문제였다

import sys
from collections import deque
input = sys.stdin.readline

N = int(input())
time = 0
road = ['A','B','C','D']
state = {'A':deque(),'B':deque(),'C':deque(),'D':deque()}
terminator = False

answer = [-1]*(N+1)

for idx in range(1,N+1):
    t, x = input().split()
    t = int(t)
    # 새로운 차량이 도로에 들어서기 전까지 도로 정리
    while time < t:
        # 1초 동안
        process = []
        for i in range(4):
            if state[road[i]] and not state[road[(i+3)%4]]:
                process.append(i)
        # 도로가 전부 비거나 교착상태에 이르면
        if not process:
            if state['A'] and state['B'] and state['C'] and state['D']:
                terminator = True
            break
        # 1초동안 처리할 수 있는 교통이 아니면
        if len(process) == 2 and abs(process[0]-process[1]) != 2:
            process.pop()
        # 교통 정리
        for i in process:
            _idx =  state[road[i]].popleft()
            answer[_idx] = time
        time += 1
    # 교착상태시
    if terminator:
        break
    # 시간 갱신
    time = t
    # 도로에 차량 추가
    state[x].append(idx)

# 도로가 교착상태에 있지 않다면 도로에 남은 차량 정리
while not terminator:
    # 1초 동안
    process = []
    for i in range(4):
        if state[road[i]] and not state[road[(i+3)%4]]:
            process.append(i)
    # 도로가 전부 비면
    if not process:
        break
    # 1초동안 처리할 수 있는 교통이 아니면
    if len(process) == 2 and abs(process[0]-process[1]) != 2:
        process.pop()
    # 교통 정리
    for i in process:
        _idx =  state[road[i]].popleft()
        answer[_idx] = time
    time += 1

# 출력
for i in range(1,N+1):
    print(answer[i])