문제 링크

문제 설명

신규 게임 ‘카카오 미로 탈출’이 출시되어, 라이언이 베타테스터로 참가했습니다.

위 예시 그림은 카카오 미로 탈출의 초기 상태를 나타냅니다. 1번부터 3번까지 번호가 붙어있는 3개의 방이 있고, 방과 방 사이를 연결하는 길에는 이동하는데 걸리는 시간이 표시되어 있습니다. 길은 화살표가 가리키는 방향으로만 이동할 수 있습니다. 미로에는 함정이 존재하며, 함정으로 이동하면, 이동한 함정과 연결된 모든 화살표의 방향이 바뀝니다.
출발지점인 1번 방에서 탈출이 가능한 3번 방까지 이동해야 합니다. 탈출하는데 걸리는 최소 시간을 구하려고 합니다.

그림의 원은 방을 나타내며 원 안의 숫자는 방 번호를 나타냅니다.
방이 n개일 때, 방 번호는 1부터 n까지 사용됩니다.
화살표에 표시된 숫자는 방과 방 사이를 이동할 때 걸리는 시간을 나타냅니다.
화살표가 가리키고 있는 방향으로만 이동이 가능합니다. 즉, 위 그림에서 2번 방에서 1번 방으로는 이동할 수 없습니다.
그림에 표시된 빨간색 방인 2번 방은 함정입니다.
함정 방으로 이동하는 순간, 이동한 함정 방과 연결되어있는 모든 길의 방향이 반대가 됩니다.
위 그림 1번 방에서 2번 방으로 이동하는 순간 1에서 2로 이동할 수 있던 길은 2에서 1로 이동할 수 있는 길로 바뀌고, 3에서 2로 이동할 수 있던 길은 2에서 3으로 이동할 수 있는 길로 바뀝니다.
똑같은 함정 방을 두 번째 방문하게 되면 원래 방향의 길로 돌아옵니다. 즉, 여러 번 방문하여 계속 길의 방향을 반대로 뒤집을 수 있습니다.
미로를 탈출하는데 필요한 최단 시간은 다음과 같습니다.
1→2: 2번 방으로 이동합니다. 이동 시간은 2입니다.
함정 발동: 2번 방과 연결된 모든 길의 방향이 반대가 됩니다.
2→3: 3번 방으로 이동합니다. 이동 시간은 3입니다.
탈출에 성공했습니다. 총 이동시간은 5입니다.
방의 개수를 나타내는 정수 n, 출발 방의 번호 start, 도착 방의 번호 end, 통로와 이동시간을 나타내는 2차원 정수 배열 roads, 함정 방의 번호를 담은 정수 배열 traps이 매개변수로 주어질 때, 미로를 탈출하는데 필요한 최단 시간을 return 하도록 solution 함수를 완성해주세요.

풀이

풀이 방법이 익숙하지 않아서 푸는데 시간이 꽤 걸렸던 문제다.

다익스트라를 쓰는 것까지는 떠올렸는데 검색을 해보고 나서야 비트마스크를 활용하는 것을 알았다.

비트마스크를 적용한 풀이는 꽤 단순하다.

트랩의 개수는 최대 10개이고 트랩이 켜지면 엣지의 방향이 변한다. 따라서 각 트랩의 상태에 따라 그래프의 모양이 달라진다.
트랩이 10개라고 가정하면 2^10개의 상태가 있을 수 있고, 이것을 비트마스크로 표현한다.

각 노드를 방문할 때마다 현재 노드와 이어진 엣지에 있는 노드의 상태를 검사한다.
1. 두 노드가 모두 꺼져있거나(함정이 아니라면 꺼진 것으로 간주한다.) 또는 모두 켜져있을 경우에는 ORIGIN 엣지를 사용한다.
2. 둘 중 한 노드만 켜져있을 경우에는 엣지의 방향이 반대이므로 REVERSED인 엣지만 사용할 수 있다.

트랩인 노드를 방문하게 되면 트랩의 상태를 바꿔준다. 이렇게 노드를 순회하다보면 트랩의 상태별로 다익스트라 배열이 존재하게 된다.

const ORIGIN = 0
const REVERSED = 1
const INF = 987654321

function solution( n, start, end, roads, traps ){
   const edges = new Array(n+1).fill().map( _ => [])
   const di = new Array(n+1).fill().map( _ => new Array( 1 << traps.length).fill(INF))
   const isTrapList = new Array(n+1).fill().map( (_,idx) => traps.findIndex( trapIdx => trapIdx === idx))
   
   roads.forEach( road => {
       const [start, end, cost] = road
       edges[start].push([cost, end, ORIGIN])
       edges[end].push([cost, start, REVERSED])
   })
   
   const trapStatus = 0
   const firstCost = 0
   
   const Q = new MinHeap()
   const firElem = makeQElement(firstCost, start, trapStatus)
   Q.push(firElem)
   
   while(Q.size()){
       const [cost, position, curTrapStatus] = Q.pop()
       
       edges[position].forEach( edge => {
           
           const [nextCost, goal, direction] = edge
           const curDirection = findEdgeDirection( position, goal, curTrapStatus, isTrapList)
           if( direction !== curDirection ) return
           
           const totalCost = cost + nextCost
           
           if(totalCost < di[goal][curTrapStatus]){
               const nextStatus = findNextTrapStatus( goal, curTrapStatus, isTrapList)
               di[goal][curTrapStatus] = totalCost
               Q.push(makeQElement(totalCost, goal, nextStatus))
           }
       })
   }
   return findMinGoal(di, end)
}

function makeQElement(cost, position, trapStatus){
   return [cost, position, trapStatus]
}

function findMinGoal( di, end ){
   return di[end].reduce( (minVal, curVal) => {
       return Math.min(minVal, curVal)
   }, INF)
}

function findNextTrapStatus( goal, trapStatus, isTrapList ){
   const trapIdx = isTrapList[goal]
   if(trapIdx === -1) return trapStatus
   return trapStatus ^ (1 << trapIdx)
}

function findEdgeDirection( curNode, goalNode, trapStatus, isTrapList){
   const curActived = isTrapActived( curNode, trapStatus, isTrapList )
   const goalActived = isTrapActived( goalNode, trapStatus, isTrapList )
   
   if( goalActived === curActived ) return ORIGIN
   return REVERSED
}

function isTrapActived( position, trapStatus, isTrapList ){
   const trapIdx = isTrapList[position]
   if(trapIdx === -1) return false
   return !!(trapStatus & 1 << trapIdx)
   
}


class MinHeap{
   constructor(){
       this._heap = [null,]
       this._rootIdx = 1
   }
   
   swap(idx1, idx2){
       [this._heap[idx1], this._heap[idx2]] = [this._heap[idx2], this._heap[idx1]]
   }
   
   size(){
       return this._heap.length - 1
   }
   
   getMaxPossibleIdx(){
       const heapLen = this._heap.length - 1
       return (heapLen / 2) >> 0
   }
   
   push(elem){
       this._heap.push(elem)
       
       let childIdx = this._heap.length - 1
       
       while(childIdx !== this._rootIdx){
           const parIdx = (childIdx / 2) >> 0
           if(this._heap[childIdx][0] < this._heap[parIdx][0]){
               this.swap(childIdx, parIdx)
               
               childIdx = parIdx
           }
           else
               break
       }
   }
   
   pop(){
       
       const popElem = this._heap[1]
       
       const leafElem = this._heap.pop()
       
       if(!this.size()) return popElem
       
       this._heap[1] = leafElem
       
       
       let curIdx = this._rootIdx
       while(this._heap[curIdx*2]){
           const leftIdx = curIdx * 2
           const rightIdx = leftIdx < this.size() - 1 ? leftIdx + 1 : -1
           const leftVal = this._heap[leftIdx][0]
           const rightVal = rightIdx === -1 ? leftVal + 1 : this._heap[rightIdx][0]
           
           const minIdx = leftVal < rightVal ? leftIdx : rightIdx
           
           if( this._heap[curIdx][0] > this._heap[minIdx][0] ){
               this.swap(minIdx, curIdx)
               curIdx = minIdx
           }
           else break
       }
       
       return popElem
   }
}