Softeer Level 3 안전운전을 도와줄 차세대 지능형 교통시스템 Python

문제 링크

https://softeer.ai/practice/6274

Softeer - 현대자동차그룹 SW인재확보플랫폼

정답 코드

import sys
from collections import deque

input = sys.stdin.readline
N, T = map(int, input().split())
rotaries = [[[] for _ in range(N)] for _ in range(N)]
for i in range(N**2):
  r = i // N
  c = i % N
  rotaries[r][c] = list(map(int, input().split()))
  
dictSign = {
  1: ["U", "R", "D"],
  2: ["L", "U", "R"],
  3: ["U", "L", "D"],
  4: ["L", "D", "R"],
  5: ["U", "R"],
  6: ["L", "U"],
  7: ["L", "D"],
  8: ["D", "R"],
  9: ["R", "D"],
  10: ["U", "R"],
  11: ["U", "L"],
  12: ["L", "D"]
}

# 현재 신호에 해당하는 번호가 있는지 확인
directionDict = {
  "U": [2, 6, 10],
  "D": [4, 8, 12],
  "L": [3, 7, 11],
  "R": [1, 5, 9]
}

udlrDict = {
  "U": 0,
  "D": 1,
  "L": 2,
  "R": 3
}

dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]

def isValid(nr, nc):
  return 0 <= nr < N and 0 <= nc < N

V = [[-1 for _ in range(N)] for _ in range(N)]

def bfs():
  sr, sc, se = 1, 0, "U"
  q = deque()
  q.append([sr, sc, se])
  while q:
    r, c, enter = q.popleft()
    nowTime = V[r][c] + 1
    if nowTime > T:
      continue
    xr = dr[udlrDict[enter]]
    xc = dc[udlrDict[enter]]
    nr = r + xr
    nc = c + xc
    if isValid(nr, nc):
      V[nr][nc] = nowTime
      nowRotarySign = rotaries[nr][nc][nowTime%4]
      # 이 번호가 directionDict에 있는지 확인
      if nowRotarySign in directionDict[enter]:
        # 있으면 다음으로 진행 가능
        for nextSign in dictSign[nowRotarySign]:
          nowSignNumber = udlrDict[nextSign]
          nextR = nr + dr[nowSignNumber]
          nextC = nc + dc[nowSignNumber]
          # 갈 수 있으면 q에 넣는다.
          if isValid(nextR, nextC):
            q.append([nr, nc, nextSign])
            
if N == 1:
  print(1)
else:
  bfs()
  result = N**2
  for line in V:
    cnt = line.count(-1)
    result -= cnt
  print(result)

풀이 방법

- 우선 교차로를 진입하는 방향을 기준으로 urldDict라는 이름으로 딕셔너리를 만든다.

- 진입한 방향에서 진행 할 수 있는 신호가 나왔는지 또 확인해줘야 하기 때문에 확인할 directionDict를 만든다.

- 어떤 신호를 받았는지 확인해줄 dictSign을 만든다. 이름은 signDict로 했으면 더 통일성 있었을 것이다.

- 처음시작은 1, 0, "U"로 해서 위로 진입하는 초기 상황을 가정한다.

    - N이 1인경우는 틀리기 때문에 N이 1이면 어차피 시간에 상관없이 교차로는 하나만 지날 수 있으므로 print(1)

- 교차로에 진입한 시간이 주어진 시간 T보다 크면 q에서 다시 꺼내게 만든다.

- 다음 진행 하는 곳이 유효하면 일단 현재 진입한 시간을 방문배열에 기록한다.

- 다음 진행 하는 곳의 로터리의 신호를 확인한 후 진행이 가능하면 q에 넣는다.

느낀점

- 실수한 점이 있다면 한 번 방문한 곳은 다시 방문하지 않는다고 해서 V[nextR][nextC] 가 -1 일 때만 진행을 시켰다.

- 이 경우 미로 같이 얽혀 있는 경우 시간을 다 소모하지 못하고 끝나게 되므로 잘못된 풀이었다.

- BFS는 비교적 자신있는 알고리즘이라 그리디나 다른 풀이에 비해 빨리 오류를 찾을 수 있었고 덕분에 빨리 풀었다.