[현대오토에버] 차세대 지능형 교통시스템

오늘 준비한 문제부터 보시죠

일부러 태그에 관련 알고리즘을 명시하지 않았습니다. 문제부터 시간을 들여 풀어보고 오시죠! 차도 한 잔 마시면서~ 산책도 좀 하면서 말이죠 ㅎㅎ. 그럼 화이팅입니다!

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

풀이 핵심 (저는 이렇게 생각했어요)

문제는 잘 풀어보셨나요? 저는 이 문제를 풀면서 아래와 같은 생각을 했어요.

• 문제를 읽으면서 2차원 배열을 만들어야겠다는 생각이 들었습니다.

• 그렇다면 2차원 배열을 단순히 순회하면서 탐색하는 것인지, 아니면 백트랙킹을 해야 하는 것인지 판단해야합니다. 이 문제는 단순탐색이었습니다. 단순탐색이기에 임시로 방문을 기록했다가 빼는 로직을 작성하지 않아도 되겠다는 생각이 들었어요.

• 순회를 허락하는 조건을 이해해야합니다.

  • 이 문제에서는 다음 좌표로 이동할 때 교차로의 진입 방향, 현재 시간, 그리고 현재시간에 따른 교차로의 신호가 순회에 영향을 줍니다.
  • 동일한 위치더라도 진입 방향에 따라 신호를 받을 수도, 아닐 수도 있음을 인지하고 이를 코드로 구현해야 합니다. 저는 처음에 문제를 제대로 안 읽고 구현을 해서 매우 많이 틀렸습니다 ㅋㅋㅋㅋㅋ.

• 교차로의 진입 방향에 대한 정의

  • 자동차는 이미 교차로의 한 가운데에 서 있고, 교차로의 진입 방향에 따라 자동차가 보고 있는 방향이 달라진다고 생각하는 편이 구현하기 쉽습니다.
  • 가령, 1번 신호는 차의 진입방향이 오른쪽이었고, 그 차가 위, 오른쪽, 아래 세 가지의 방향을 갈 수 있다는 신호로 이해하는거죠.
  • 저는 처음에는 대각선 위, 오른쪽, 대각선 아래로 코드를 작성했다가 구현이 매우 복잡해져 다시 코드를 작성했습니다.

코드

const intersectionInfo = require('fs')
  .readFileSync(0)
  .toString()
  .trim()
  .split('\n')
  .map((line) => line.split(' ').map(Number))
const [N, T] = intersectionInfo.shift()

//신호번호에 따라 갈 수 있는 방향을 기록한 객체
const signalInfo = {
  1: ['up', 'right', 'down'],
  2: ['left', 'up', 'right'],
  3: ['up', 'left', 'down'],
  4: ['left', 'down', 'right'],
  5: ['up', 'right'],
  6: ['left', 'up'],
  7: ['left', 'down'],
  8: ['down', 'right'],
  9: ['right', 'down'],
  10: ['up', 'right'],
  11: ['up', 'left'],
  12: ['left', 'down'],
}

//진입 방향에 따라 진행할 수 있는 신호를 기록한 객체
const availableSignals = { up: [2, 6, 10], right: [1, 5, 9], down: [4, 8, 12], left: [3, 7, 11] }

//진행 방향에 따라 row, column의 변화(delta)를 기록한 객체
const dirToDelta = { up: [-1, 0], right: [0, 1], down: [1, 0], left: [0, -1] }

//유효한 2차원 배열 좌표값인지 검증하는 함수
function validateCoorditate(x, y) {
  return x >= 0 && y >= 0 && x < N && y < N
}

//중복으로 세는 것을 방지하기 위해 방문을 기록하는 2차원 배열
const visitedMap = Array.from(Array(N), () => new Array(N).fill(0))

let answer = 0

//본격적인 재귀함수 - dfs방식의 탐색을 실행하기 위함
function recursion({ currentRow, currentColumn }, currDir, currentT) {
  //재귀 종료 조건 - 유효한 시간이 아닐 때
  if (currentT > T) {
    return
  }
  //현재 좌표는 유효하니 방문처리를 해줌
  if (visitedMap[currentRow][currentColumn] === 0) {
    visitedMap[currentRow][currentColumn] = 1
    answer++
  }
  //현재 몇 번째 교차로에 있는지
  const currentIntersectionIndex = currentRow * N + currentColumn
  //이 교차로는 현재 어떤 신호를 주고 있는지
  const currentSignal = intersectionInfo[currentIntersectionIndex][currentT % 4]
  //현재 교차로의 신호가 진입 방향에 유효한지 ~ 유효하면 진행시켜!
  if (availableSignals[currDir].includes(currentSignal)) {
    const candidateDirections = signalInfo[currentSignal]
    //신호에 따라서 진행방향이 여러개니, for문을 통해 각각 순회
    for (const nextDir of candidateDirections) {
      const [rowDelta, columnDelta] = dirToDelta[nextDir]
      const nextRow = currentRow + rowDelta
      const nextColumn = currentColumn + columnDelta
      //다음에 방문할 좌표가 유효한 좌표일때만 재귀 진행
      if (!validateCoorditate(nextRow, nextColumn)) continue
      //쪼로록~ 선택한 방향으로 다음 탐색을 이어 진행합니다
      recursion({ currentRow: nextRow, currentColumn: nextColumn }, nextDir, currentT + 1)
    }
  }
}

recursion({ currentRow: 0, currentColumn: 0 }, 'up', 0)

console.log(answer)

총평 및 회고

• 구현문제 + 2차원 배열 순회는 자주 등장하는 주제입니다. 실제로 풀이를 보면 몇 줄 되지 않습니다. 전형적인 DFS에요.
• 문제에서는 장황하게 핵심 개념을 장황한 설명으로 애써 숨기고 있습니다. 특히 12개의 신호 이미지가 심리적으로 압박감을 주더군요. 어떻게 해서든 최적화해서 깔끔하게 신호 방향을 기록하는 데이터를 만들려고 하는 순간, 시간을 낭비하게됩니다.
• 그래서 느낀 점은 일단 노가다로 구현하고 최적화는 나중에였습니다.
  완벽주의를 버리고, 내 논리대로 문제의 핵심로직을 완성하는데 초점을 두는 것이 시간을 아끼는 지름길 같습니다.