[Softeer] S580 안전운전을 도와줄 차세대 지능형 교통시스템

[Softeer]

Question

Language: Python

해당 문제는 교차로를 지나면서, 각각의 교차로에 해당되는 신호에 따라 이동을 하면서 지나갈 수 있는 교차로의 갯수를 구하는 문제이다.

각각의 교차로 마다, 신호의 주기는 고정되어 있으므로, 신호에 대해서 어떤 방향으로 이동을 하는지에 대한 배열을 저장한 다음, 재귀문을 활용하여 시뮬레이션을 진행하면 된다.

각 교차로별 신호

directions=[(1,0),(0,1),(-1,0),(0,-1)]
transitions=[0,
    [2,1,0],
    [3,2,1],
    [0,3,2],
    [1,0,3],
    [2,1],    
    [3,2],
    [0,3],
    [1,0],
    [1,0],
    [2,1],    
    [3,2],
    [0,3]
]    

해당 신호 체계를 유심히 보면 1,5,9 번의 신호는 동쪽 방향으로 2,6,10 번의 신호는 북쪽 방향으로 3,7,11 번의 신호는 서쪽 방향으로 4,8,12 번의 신호는 남쪽 방향으로 교차로를 통과했을 때 이동이 가능한 신호들이다. 따라서, 이러한 정보를 활용하여 해당 교차로에 특정 신호가 들어왔을때, 방향이 일치하지 않으면 해당 경우에 대해서는 고려하지 않아도 된다.

#각각의 교차로는 총 4개의 신호가 반복하기 때문에, 특정 시간에 대한 신호를 구하기 위해 4의 나머지값을 활용한다.
signal=crossways[row][col][index%4]
#해당 신호와 자동차의 방향이 일치하지 않는 경우 교차로 통과 불가능
if signal % 4 != dir:
    return

또한, 각각의 교차로에 대해서, 신호, 방향을 함께 고려하여 방문 정보를 저장하므로써, 추후에 중복된 검사를 피하도록 한다.

visited=[[[[False] *4 for _ in range(4)] for _ in range(n)] for _ in range(n)]
#이전에 방문했는지 여부(방향도 함께 저장)
if visited[row][col][dir][index%4]:
    return
visited[row][col][dir][index%4]=True

Solution

import sys
from math import inf

def solution(index,row,col,dir):
    global passed_crossways,visited
    
    passed_crossways.add((row,col))
    if index==t:
        return
    signal=crossways[row][col][index%4]
    
    #해당 신호와 자동차의 방향이 일치하지 않는 경우 교차로 통과 불가능
    if signal % 4 != dir:
        return

    #이전에 방문했는지 여부(방향도 함께 저장)
    if visited[row][col][dir][index%4]:
        return
    visited[row][col][dir][index%4]=True

    for next_dir in transitions[signal]:
        next_row=row+directions[next_dir][0]
        next_col=col+directions[next_dir][1]

        #범위를 넘어서는 경우 해당 교차로 통과 불가능
        if next_row < 0 or next_row>=n or next_col < 0 or next_col>=n:
            continue
        solution(index+1,next_row,next_col,next_dir)
    


if __name__ == "__main__":
    n,t=map(int,sys.stdin.readline().split())
    crossways=[[list(map(int,sys.stdin.readline().split())) for _ in range(n)] for _ in range(n)]    
    passed_crossways=set()

    transitions=[0,
       [2,1,0],
       [3,2,1],
       [0,3,2],
       [1,0,3],
       [2,1],    
       [3,2],
       [0,3],
       [1,0],
       [1,0],
       [2,1],    
       [3,2],
       [0,3]
    ]

    visited=[[[[False] *4 for _ in range(4)] for _ in range(n)] for _ in range(n)]

    directions=[(1,0),(0,1),(-1,0),(0,-1)]
    
    #index, row,col, dir
    #direction: 남:0 동:1, 북:2, 서:3, 
    solution(0,0,0,2)

    print(len(passed_crossways))