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

정답 코드

import sys

N, T = map(int, sys.stdin.readline().split())
go = [[],[1,0], [-1,0], [0,-1], [0,1]] #동 서 북 남
way = {1:go[1], 2:go[2], 3:go[3], 4:go[4], 5:go[3], 6:go[1], 7:go[4], 8:go[2], 9:go[4], 10:go[2], 11:go[3], 12:go[1]}
tl = [[], [1, 5, 9], [8, 3, 12], [11, 2, 7], [10, 4, 6], [5, 1], [8, 3], [2, 7], [4, 6],
      [1, 9], [3, 12], [11, 2], [10, 4]]
direction = [[3, 8, 12], [1, 5, 9], [4, 6, 10], [2, 7, 11]]  # 0북 1동 2남 3서
sig = [[] for i in range(N)]
v = [[False for i in range(N)] for j in range(N)]
check = [[[[False for i in range(101)] for j in range(4)] for k in range(101)] for o in range(101)]
for i in range(N):
    for j in range(N):
        sig[i].append(list(map(int, sys.stdin.readline().split())))

queue = [[0, 0, 0, 0]]  # row, col, direction, time
ans = 1
v[0][0] = True
check[0][0][0][0] = True

while len(queue) > 0:
    curr = queue[0]
    del queue[0]
    time = curr[3]
    d = curr[2]

    num = sig[curr[0]][curr[1]][time % 4]  # traffic light number
    for i in direction[d]: # 현재 방향이 갈 수 있는 신호를 받아 와서
        if i in tl[num]: # 만약 현재 교차로 신호등에 갈 수 있는 신호가 있으면
            pr = way[i][1] # row 방향 값
            pc = way[i][0] # col 방향 값

            nr = curr[0] + pr
            nc = curr[1] + pc
            if pr == -1:
                temp_d = 0
            elif pr == 1:
                temp_d = 2
            elif pc == 1:
                temp_d = 1
            else:
                temp_d = 3
            if 0 <= nc < N and 0 <= nr < N and not check[nc][nr][temp_d][(time + 1) % 4]:
                if time + 1 <= T:
                    check[nc][nr][temp_d][(time + 1) % 4] = True
                    queue.append([nr, nc, temp_d, time + 1])
                    if not v[nr][nc]:
                        v[nr][nc] = True
                        ans += 1
    queue = list(set(map(tuple, queue)))
    if ans == N * N:
        break

print(ans)

알고리즘 유형

BFS

풀이 방법

BFS(Breadth-First-Search) 탐색을 통해 시간을 기준으로 상황을 시뮬레이션 하듯 풀이를 합니다 .

이 때, 각 교차로마다 입력값이 다르기에 해당 정보를 저장해놓고 현재 시간을 기준으로 내가 이동할 수 있는 방향을 조회합니다. 여기서 4가지 상태를 무한히 반복하므로 T%4 상황으로 정리할 수 있습니다.

하지만 사이클이 발생할 가능성이 있기에 방문처리가 필요합니다. T초 상황과 T+4초 상황일때 같은 방향에서 들어오는 경우라면, T+1초와 T+5초의 상황은 동일합니다.

즉, 같은 상황이 여러번 반복됨으로 불필요하게 탐색하지 않아도 되는 상황입니다.

그리하여 방문처리 check 배열(check[time][dir][x][y])을 두어 위의 불필요한 상황을 해결 할 수 있습니다.

마지막으로 방문했던 교차로를 찾기 위해 check 배열을 4중 for문을 통해 방문한 교차로를 카운트 해줍니다.

배운 점

time과 time + 4가 같고, time + 1과 time + 5가 같다는 사실을 코드로 구현하지 않아
시간 초과 문제가 있었다. 이 때문에 풀이가 오래 걸렸는데 반복되는 경우 time complexity를 낭비하지 않도록 신경써야겠다.

후기

역시 PS는 풀고나면 상쾌하다