[Softeer인증시험1차 기출] 안전운전을 도와줄 차세대 지능형 교통시스템(파이썬)

 

bfs와 노가다가 합쳐진 문제.

문제 길이가 길어서

문제를 이해하는 데 좀 오래거렸지만

이해하면 간단하게 풀 수 있는 문제.

 

1. 로봇의 방향+신호가 맞아야함

-->

가장 먼저, 각 신호에 대해서 dic으로 

해당 신호일 때 움직이는 방향들을 각각 구했습니다.

현재 움직인 시간을 cnt로 두고

현재 시간은 cnt%4로 설정했습니다.

그 후, 현재 방향과 알맞는 신호가 올 때 움직이는 것으로 구했습니다.

예를들면, 현재 자동차 방향이 위라면 2,6,10이어야 움직이도록 설정했습니다.

 

2. 신호에 따라 움직이기

-->dic에 각 신호에 따라 움직이는 걸 구했기 때문에 

이제는 간단합니다.

dic[현재신호]를 불러온 다음

자동차가 해당 신호대로 움직일 수 있는지 구합니다.

범위를 넘지 않는다면

visited set()에 넣어줍니다.

set()은 중복을 자동으로 걸러주기 때문에

해당 지점이 visited에 있는지 없는지 여부를 굳이 체크할 필요가 없습니다.

움직임을 마친 뒤에, visited의 길이를 구하면 끝.

 

import sys
from collections import deque

N, T = map(int, input().split())
maps = [[[] for _ in range(N)] for _ in range(N)]
for i in range(N ** 2):
    x = i // N
    y = i % N
    a, b, c, d = map(int, input().split(" "))
    maps[x][y] = [a, b, c, d]
dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0]
signal = {
    1: [0, 1, 3],
    2: [0, 1, 2],
    3: [1, 2, 3],
    4: [0, 2, 3],
    5: [0, 1],
    6: [1, 2],
    7: [2, 3],
    8: [0, 3],
    9: [0, 3],
    10: [0, 1],
    11: [1, 2],
    12: [2, 3]

}

visited = set()
visited.add((0, 0))

q = deque()
q.append((0, 0, 1, 0))

while q:

    x, y, nd, cnt = q.popleft()

    if cnt == T:
        continue

    now_time = cnt % 4
    now_signal = maps[x][y][now_time]
    # print(x,y,nd,cnt,now_signal)
    # 현재 방향에 따라 교차로 진입여부 설정
    if nd == 0:
        if now_signal in (1, 5, 9):
            pos = signal[now_signal]
            for go in pos:
                nx = x + dx[go]
                ny = y + dy[go]

                if nx < 0 or nx >= N or ny < 0 or ny >= N:
                    continue
                visited.add((nx, ny))
                q.append((nx, ny, go, cnt + 1))
    elif nd == 1:
        if now_signal in (2, 6, 10):
            pos = signal[now_signal]
            for go in pos:
                nx = x + dx[go]
                ny = y + dy[go]

                if nx < 0 or nx >= N or ny < 0 or ny >= N:
                    continue
                visited.add((nx, ny))
                q.append((nx, ny, go, cnt + 1))
    elif nd == 2:
        if now_signal in (3, 7, 11):

            pos = signal[now_signal]
            for go in pos:
                nx = x + dx[go]
                ny = y + dy[go]

                if nx < 0 or nx >= N or ny < 0 or ny >= N:
                    continue
                visited.add((nx, ny))
                q.append((nx, ny, go, cnt + 1))

    elif nd == 3:
        if now_signal in (4, 8, 12):
            pos = signal[now_signal]
            for go in pos:
                nx = x + dx[go]
                ny = y + dy[go]

                if nx < 0 or nx >= N or ny < 0 or ny >= N:
                    continue
                visited.add((nx, ny))
                q.append((nx, ny, go, cnt + 1))

print(len(visited))