[softeer] [인증평가(1차) 기출] 안전운전을 도와줄 차세대 지능형 교통시스템 (python)

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

Softeer

---

문제 회고

 

bfs를 이용해서 경로를 찾아주면 된다. 하나 신경 쓸 부분은 해당 교차로에 오는 방향에 따라 다음 교차로로 갈 수 있냐 없냐가 정해진다는 점이다.

처음에는 당연하게 check list를 만들어서 방문한 교차로는 다시 방문하지 않도록 하였는데 계속해도 틀려서 조금 검색을 해보았더니 방문한 교차로도 돌고 돌면서 최종적으로 갈 수 있는 교차로를 모두 구하는 문제였다.

문제를 잘 이해하는 것이 중요할 것 같다. 변수 이름 짓기도 너무 어렵다...

---

import sys
from collections import deque

n, t = map(int, sys.stdin.readline().split())
check = [[False] * (n + 1) for _ in range(n + 1)]
signals = [[[]] * (n + 1) for _ in range(n + 1)]
move = {'up': (-1, 0), 'down': (1, 0), 'left': (0, -1), 'right': (0, 1)}
traffic = {
    1: (move['right'], [move['up'], move['right'], move['down']]),
    2: (move['up'], [move['left'], move['up'], move['right']]),
    3: (move['left'], [move['up'], move['left'], move['down']]),
    4: (move['down'], [move['right'], move['down'], move['left']]),
    5: (move['right'], [move['up'], move['right']]),
    6: (move['up'], [move['left'], move['up']]),
    7: (move['left'], [move['left'], move['down']]),
    8: (move['down'], [move['down'], move['right']]),
    9: (move['right'], [move['right'], move['down']]),
    10: (move['up'], [move['up'], move['right']]),
    11: (move['left'], [move['up'], move['left']]),
    12: (move['down'], [move['left'], move['down']])
}

for i in range(1, n + 1):
    for j in range(1, n + 1):
        signal = list(map(int, sys.stdin.readline().split()))
        signals[i][j] = signal

answer = set()
def bfs():
    q = deque()
    q.append(((1, 1), (-1, 0), 0))

    while q:
        now, prev_move, now_time = q.popleft()
        answer.add((now[0], now[1]))
        now_signal = signals[now[0]][now[1]][now_time%4]
        move = traffic[now_signal]
        if prev_move != move[0]:
            continue
        for nx, ny in move[1]:
            dx, dy = now[0] + nx, now[1] + ny
            if 1 <= dx <= n and 1 <= dy <= n:
                if not check[dx][dy] and now_time < t:
                    q.append(((dx, dy), (nx, ny), now_time + 1))
        
bfs()
print(len(answer))