[소프티어] [인증평가(3차) 기출] 교차로 (파이썬)

난이도 : ★★★☆☆

 

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

Softeer

 

📄 문제

• 자율주행차가 교차로를 통과하는 상황
• A, B, C, D 각 도로의 맨 앞에 있는 자동차는 자신을 기준으로 오른쪽에 위치한 도로에 차량이 있으면 1초 동안 출발하지 않고, 차량이 없으면 즉시 교차로를 통과한다. (반시계 방향에 차가 있으면 출발하지 않고 1초 기다림)
  • A 위치에 있는 차량의 오른쪽에 있는 도로는 D
  • B 위치에 있는 차량의 오른쪽에 있는 도로는 A
  • C 위치에 있는 차량의 오른쪽에 있는 도로는 B
  • D 위치에 있는 차량의 오른쪽에 있는 도로는 C

 

• 안전을 위해 각 위치마다 1초에 한 대씩만 교차로를 통과할 수 있다.
• A, B, C, D 위치에 동시에 차량이 한 대 이상씩 있다면, 교착 상태에 빠져 어떤 차량도 교차로를 통과할 수 없게 된다.
• 같은 시각에 각 위치에 진입할 수 있는 차량은 최대 한 대이다.

 

매초마다 모든 차량이 진입한 직후, 각 위치의 맨 앞에 있는 차량은 오른쪽 위치에 차량이 없는지 확인한 뒤, 차량이 없다면 교차로를 통과한다. 각 차량이 교차로를 통과하는 시각이 언제인지 계산하는 프로그램을 작성하라.

 

---

💡 아이디어

1. 각 도로마다 자동차 번호와 시간을 저장한다.
   • deque() 에 저장
   • 차량이 진입한 순서대로 저장하여 앞에서 부터 체크
2. 현재 시간을 설정한다.
3. 현재 시간에 자동차가 통과 가능한지 체크한다.
   • 각 도로에 맨 앞 차량이 진입한 시간이 현재 시간보다 작거나 같은 지 체크
   • 현재 시간에 각 도로의 오른쪽 도로에 자동차가 존재하는지 체크
   • True / False
4. 교착 상태인지 체크한다.
   • 현재 시간에 각 도로에 모두 자동차가 존재하는지 체크
   • 각 도로에 남아 있는 자동차 진입 시간이 현재 시간보다 작거나 같은 지 체크
   • 교착 상태가 되면 탐색을 중단
5. 통과 가능한 차량은 교차로를 통과 시킨다.
   • 통과 가능한 차량은 각 차량 번호에 통과한 시간을 저장한다.
   • 통과한 차량은 해당 도로에서 popleft() 로 제거한다.

 

반응형

 

📝 문제 풀이 (Code)

import sys
from collections import deque

n = int(input())

# n번 차량 통과 시간 저장
ans = [-1]*n

# a, b, c, d 위치 차량 정보
road = {'A':deque(), 'B':deque(), 'C':deque(), 'D':deque()}

# 오른쪽에 위치한 도로
rightCar = {'A':'D', 'B':'A', 'C':'B', 'D':'C'}


for i in range(n):
    t, w = input().split()

    road[w].append((int(t), i))

    # 시작 시간
    if i == 0:
        currTime = int(t)

maxV = 1000000001


while road['A'] or road['B'] or road['C'] or road['D']:

    # 남아 있는 차량의 최소 값
    minV = maxV
    
    # 각 도로의 방문 차량 최소 값 체크
    minVisited = {'A':0, 'B':0, 'C':0, 'D':0}

    # 현재 시각 도로에 차량 존재 하는지 체크
    isCar = {'A':False, 'B':False, 'C':False, 'D':False}

    # 교착상태 확인
    isDeadlock = 0


    for p in ['A', 'B', 'C', 'D']:
        # 값이 있을 때
        if road.get(p):
            t, _ = road[p][0]
            # 현재 가장 빠른 방문 차량
            minVisited[p] = t

            # 차량 시간 체크
            minV = min(minV, t)
			
            # 현재 교차로에 존재하는 차량 수 (각 도로 당 1) 
            if t <= currTime:
                isDeadlock += 1

        else:
            minVisited[p] = maxV

    # 교착상태 체크
    if isDeadlock == 4:
        break

    # 기다리는 차량이 없으면 현재 시간 다가 올 차량 시간으로 갱신
    if isDeadlock == 0:
        currTime = minV


    for p in ['A', 'B', 'C', 'D']:
        
        # 현재 시간 까지 도착한 차량이고
        if minVisited[p] <= currTime:

            # 오른쪽 위치에 차량이 현재 시간 이후에 도착
            if road.get(rightCar[p]):
                if minVisited[rightCar[p]] > currTime:
                    isCar[p] = True
            else:
                # 오른쪽 차량 존재 안함
                isCar[p] = True


    # 통과 가능한 차량에 시간 저장
    for p in ['A', 'B', 'C', 'D']:
        if isCar[p]:
            _, num = road[p].popleft()
            ans[num] = currTime

    currTime += 1
        

# 각 차량의 통과 시간 출력
for k in ans:
    print(k)