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

HSAT 1회 정기 코딩 인증 평가 기출 문제 중 "안전운전을 도와줄 차세대 지능형 교통시스템" 문제를 풀이하고 있습니다.

 

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

 

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

 

1. 원리

2. 코드

추천글

위의 목차를 클릭하면 해당 글로 자동 이동 합니다.

 

원리

• 1회 기출이어서 그런가 당연하게 탐색 문제였고, BFS를 사용하면 쉽게 해결할 수 있었다.
• 사실 방향을 막 조정하는 것은 그렇게 어려운 것이 아니었고, 신호들을 일일히 컨트롤해도 아마 쉽게 풀 수 있었을 것이라고 생각한다.
• 하지만, 간단한 문제 요구 사항과는 다르게 조심해야 할 것들이 몇 가지 존재한다.
• 그 부분에 대해서 설명을 하고 넘어가도록 할 것이다.
  • 기본적인 (x, y) 형태의 2차원 배열을 쓸 때, 컴퓨터 공학에서는 x가 행이고 y가 열이다.
  • 이것은 선대수의 행렬에서도 마찬가지인데, 이 문제에서는 (x, y)가 반대로 되어있다.
    • x가 증가하면 가로 방향으로 오른쪽 이동이며 y가 증가하면 세로 방향으로 아래로 이동한다.
  • 그래서 특정 교차로의 신호 집합을 가져와야 할 때, 넘버링이 잘못될 수 있다.
    • 원래라면 x * N + y로 계산할 수 있지만, 위와 같이 짜여져 있다면 y * N + x 가 되어야 한다.
  • 두 번째는 visited 배열을 만들고, 방문 확인을 하게 될 텐데 이 문제에서는 방문했던 교차로를 다시 방문하지 말라는 소리가 없다.
  • 그 대신 방문했던 교차로는 카운트하지 않는 것이다.
  • 나도 초기에는 방문한 교차로를 재방문하지 않도록 로직을 짰고 그러면 T가 다 흐르기 전에 로직이 종료가 되는 경우가 있다.
  • 하지만 문제가 의도한 바는 T라는 시간만큼 계속 이동하면서 중복없이 몇 개의 교차로를 방문했는지이다.
• 그리고 아래에서 보여줄 코드에서 이해하기 힘든 부분이 한 가지 있을 것 같아 그 부분에 대해 설명한다.
  • 아래의 코드는 r == 0인 경우, r ==1인 경우, 그리고 r==2인 경우를 나눠서 생각한다.
  • 그 이유는 1, 2, 3, 4 신호, 배열 인덱스로는 0, 1, 2, 3 신호는 해당 신호가 보는 방향에서 90도 왼쪽과 90도 오른쪽 모두 갈 수 있다.
    • 따라서 4로 나눈 몫이 0이면 3가지 경우를 모두 탐색한다.
  • 5, 6, 7, 8 신호, 배열 인덱스로는 4, 5, 6, 7 신호는 해당 신호가 보는 방향에서 90도 왼쪽 방향으로만 갈 수 있다.
    • 따라서 4로 나눈 몫이 1이면 2가지 경우만 탐색한다.
  • 마지막 9, 10, 11, 12 신호, 배열 인덱스로는 8, 9, 10, 11 신호는 해당 신호가 보는 방향에서 90도 오른쪽 방향으로만 갈 수 있다.
    • 따라서 4로 나눈 몫이 2이면 2가지 경우만 탐색한다.
• 그 외에는 이해하기 어려운 부분은 없을 것 같다.

코드

import sys
from collections import defaultdict, deque

def isInTheMap(x, y):
    global N
    if x > -1 and x < N and y > -1 and y < N:
        return True
    return False

dir = ['R', 'U', 'L', 'D']

# 오른쪽, 위, 왼쪽, 아래
dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]

N, T = map(int, sys.stdin.readline().split(" "))

signSet = defaultdict(list)

for iter in range(N**2):
    set = list(map(int, sys.stdin.readline().strip().split(" ")))
    signSet[iter] = set

visited = [[False for _ in range(N)] for _ in range(N)]
q = deque()

q.append([0, 0, 'U', 0])
answer = 0
while q:
    data = q.popleft()
    cx = data[0]
    cy = data[1]
    direction = data[2]
    t = data[3]
    if t > T:
        continue
        
    # 몇 번 신호인지, 4가지 상태를 무한히 반복하므로,,,
    signNumber = signSet[cy * N + cx][t % 4] - 1

    if not visited[cx][cy]:
        answer += 1
    visited[cx][cy] = True

    # 신호가 가르키는 방향
    signDir = dir[signNumber % 4]
    if direction != signDir:
        # 다르면 더 이상 진행 불가능
        continue
    
    # 신호를 통해서 갈 수 있는 교차로
    r = signNumber // 4
    m = signNumber % 4

    if r == 0:
        for i in [(m+4-1) % 4, m, (m+1) % 4]:
            nx = cx + dx[i]
            ny = cy + dy[i]
            if isInTheMap(nx, ny):
                q.append([nx, ny, dir[i], t+1])
    elif r == 1:
        for i in [m, (m+1) % 4]:
            nx = cx + dx[i]
            ny = cy + dy[i]
            if isInTheMap(nx, ny):
                q.append([nx, ny, dir[i], t+1])
    elif r == 2:
        for i in [(m+4-1) % 4, m]:
            nx = cx + dx[i]
            ny = cy + dy[i]
            if isInTheMap(nx, ny):
                q.append([nx, ny, dir[i], t+1])
print(answer)

 

BFS 문제라서 아직은 그리 어렵지 않게 풀었다. 하지만 제출은 10번 정도를 했는데 본문에서 언급했던 문제들을 간과해서 그랬다. 1회차 1번 문제가 조금 쉬워서 메모를 하지 않고 바로 코딩을 했던 나는 반성할 필요가 있다.

 

추천글

https://softeer.ai/class/devcrew/study/resource/detail/description/6274?id=245&resourceId=282

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