[Softeer] HSAT 1회 기출 - 안전운전을 도와줄 차세대 지능형 교통시스템

문제

<배경>

 

<문제풀이와 직접적 연관 없는 배경↓>

자율주행차가 영화 속 자율주행차와 다른 이유는 차량 자체의 센서 기술은 발달했지만, 교통 인프라는 도입되지 않았기 때문이다. 이 때, 필요한 것이 바로 차세대 지능형 교통 시스템이다. 통상 ITS는 지능형 교통시스템(Intelligent Transport System)을 이야기 한다.

 

ITS는 이미 우리의 삶에 밀접하게 연결되어 있다. 내비게이션 실시간 교통정보, 고속도로의 하이패스, 정류장의 버스 도착 안내 시스템들이 ITS에 속한다. 여기서 차량과 인프라가 서로 협력하면 차세대 지능형 교통시스템(C-ITS, Cooperative Intelligent Transportation System)이 되는 것이다. 이렇게 차량 주행과 관련된 인프라와 차량 등이 통신하기 시작하면 사고나 정체 상황에서 놀라운 일이 벌어진다.

 

<문제설명>

여기 교통 인프라(신호등)와 실시간 통신을 하는 자율주행 자동차가  $N$크기(가로: $N$, 세로: $N$)도로를 지나고 있다. 격자 간 연결된 선을 도로, 각 선(도로)의 교차점들을 교차로로 생각하자. 자율주행 자동차는 처음에 제일 왼쪽 위의 교차로로 아래쪽 방향에서 진입하고 있다. (자동차는 격자의 한 칸을 가는 데는 1분이 걸린다.)

각 교차로의 신호등은 다음과 같은 12가지 상태 중 4가지를 가지고 무한히 반복하는 방식으로 운영된다.

자율주행 자동차가 멈추지 않고, 시간 $T$(분) 이내에 갈 수 있는 교차로의 수를 계산하라.

단, 신호가 맞지 않으면 그 교차로에는 갈 수가 없다.

처음에 제일 왼쪽 위의 교차로로 아래쪽 방향에서 진입하고 있으므로, 교차로(1,1)의 신호가 2, 6, 10번 중 하나가 아니면 갈 수 있는 교차로가 단 하나교차로(1,1)로 계산한다.

 

<입력>

<출력>

이동 경로에 있는 모든 교차로의 개수를 출력한다. 한번 갔던 교차로는 중복해서 세지 않는다.

 

<예시>

---

풀이

제약조건이 값이 크지 않으므로 그냥 모든 경우를 시뮬레이션하는 코드를 작성하자.

n,t = map(int,input().split())
signal = []

for row in range(n):
    temp = []
    for col in range(n):
        temp.append(list(map(int, input().split())))
    signal.append(temp)

 

이제 문제에서 준 12가지의 신호 종류를 저장할 배열을 만들어야한다.

먼저 0,1,2,3을 9시 6시 3시 12시 방향을 나타낸다고 하자.

각 신호에 대해 4*4행렬을 만들어서 [들어온방향][나가는방향]에 대해 1을 저장한다.

이런 신호가 12개가 있으므로 4*4행렬이 12개가 있는 행렬이 만들어질 것이다.

신호는 0번이 아닌 1번부터 시작하므로 range(13)을 사용했다.

 

신호1~신호4에 대해 값을 작성하면 아래와 같다.

signalInfo = [[[0 for _ in range(4)] for _ in range(4)] for _ in range(13)] #4x4행렬 12개
#0,1,2,3 : 9시 6시 3시 12시 , 들어와서 나가는 방향
signalInfo[1][0][1] = signalInfo[1][0][2] = signalInfo[1][0][3] = 1 
signalInfo[2][1][2] = signalInfo[2][1][3] = signalInfo[2][1][0] = 1
signalInfo[3][2][3] = signalInfo[3][2][0] = signalInfo[3][2][1] = 1
signalInfo[4][3][0] = signalInfo[4][3][1] = signalInfo[4][3][2] = 1

하지만 보면 신호1~4, 신호5~8, 신호9~12는 각각 같은 신호를 방향만 돌린 것임을 알 수 있다.
따라서 일일히 값을 작성하지 않고 아래처럼 조금 간단히 모든 신호에 대해 값을 작성할 수 있다.

for i in range(4):
    signalInfo[i+1][i][(i+1)%4] = 1 #신호1~4
    signalInfo[i+1][i][(i+2)%4] = 1
    signalInfo[i+1][i][(i+3)%4] = 1

    signalInfo[i+5][i][(i+2)%4] = 1 #신호5~8
    signalInfo[i+5][i][(i+3)%4] = 1

    signalInfo[i+9][i][(i+1)%4] = 1 #신호9~12
    signalInfo[i+9][i][(i+2)%4] = 1

 

이제 차의 상태와 관련된 변수들을 만들자.

차가 어떤 교차로에 있는지 나타낼 변수 junction이 있다.

단순히 n*n으로 만들어 해당 교차로의 값을 1로 만들면 된다고 생각할 수 있는데, 차가 들어오는 방향이 중요하므로 n*n개의 교차로 각각에 대해 방향을 나타낸 길이4의 리스트를 원소로 가지게 했다.

처음 시작은 1번 교차로의 아래(방향 1)에서 차가 들어오는 것으로 시작하므로

junction[0][0][1] = 1 로 초기값 세팅을 해줬다.

 

junction2는 junction의 상태에서 1초가 지난 후 차의 상태를 저장하는 행렬이다.

junction2에서 1초 뒤의 상태는 다시 junction에 기록하는 방식으로 코드를 작성할 것이다.

visit은 문제의 답을 내는데 필요한 방문한 교차로를 저장하는 배열이다.

junction = [[[0 for _ in range(4)] for _ in range(n)] for _ in range(n)] #차가 어디있는지 기록, 방향까지(4)
junction[0][0][1] = 1 #시작상태 : 1번 교차로 아래(1)에서 차 들어옴
junction2 = [[[0 for _ in range(4)] for _ in range(n)] for _ in range(n)] #junction에서 1초 뒤
visit = [[0 for _ in range(n)] for _ in range(n)]
visit[0][0] = 1

 

이제 시뮬레이션을 하는 코드를 작성하자.

주어진 시간동안, 모든 행,열(각 교차로)에 대해, 특정방향에서 들어오는 차가 있을 때만 어떤방향으로 나갈 수 있는지 보고 update한다.

update를 한 결과는 다른 junction 배열에 저장될 것이므로 들어왔던 방향의 값은 0으로 다시 초기화 해준다.

for time in range(t):
    for row in range(n):
        for col in range(n):
            for inDir in range(4):
                if junction[row][col][inDir]: #이 방향에서 들어오는 차가있을 때만
                    for outDir in range(4):
                        update(time,row,col,inDir,outDir,junction,junction2)
                    junction[row][col][inDir] = 0
    junction, junction2 = junction2, junction

 

마지막으로 update함수를 구현한다.

signalNow에는 현재 교차로에 켜진 신호가 몇 번 신호인지를 저장한다.

현재 차가 들어온 방향에서 나가는 방향의 신호가 켜져있을 때 outDir의 방향에 따라 이후 행동을 해준다.

 

예시로 outDir=0일 때의 경우를 보자.

어디서 들어왔던지 왼쪽(0)의 교차로로 나가는 것이므로 junction2에서는 해당교차로의 오른쪽(2)에서 차가 들어오는 것이다.

또 나가는 곳의 교차로는 방문이 된것이므로 visit배열에 추가해준다.

이때 col 이 이미 0이었다면 더 왼쪽에는 교차로가 없는 것이므로 이 경우는 빼준다.

def update(time,row,col,inDir,outDir,junction,junction2):
    signalNow = signal[row][col][time%4] #지금 신호 번호
    if signalInfo[signalNow][inDir][outDir]: #지금 신호 번호가 켜졌을 때 나갈 수 있으면
        if outDir==0 and col != 0:
            junction2[row][col-1][2] = 1
            visit[row][col-1] = 1
        elif outDir==1 and row != n-1:
            junction2[row+1][col][3] = 1
            visit[row+1][col] = 1
        elif outDir==2 and col != n-1:
            junction2[row][col+1][0] = 1
            visit[row][col+1] = 1
        elif outDir==3 and row != 0:
            junction2[row-1][col][1] = 1
            visit[row-1][col] = 1
    return

 

이제 visit배열에서 방문한 교차로의 수를 세서 프린트한다.

count = 0
for row in range(n):
    for col in range(n):
        if visit[row][col] == 1:
            count += 1
print(count)

변수가 많고 for문이 다섯번씩 중첩되기때문에 복잡한 문제였다.