[Programmers] 미로 탈출

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/81304

프로그래머스

 
함정의 개수가 최대 10개이므로 비트마스킹과 다익스트라 알고리즘을 사용하는 문제였습니다.
 
알고리즘은 다음과 같습니다.
1. 주어진 파라미터를 토대로 전처리를 진행합니다.

• traps에 포함된 방 번호에 대해 각 방을 bitmask의 몇 번째 비트에 매핑할지 결정 (trap2idx)
• 원래 방향의 edge (u -> v)는 현재 상태에서 u의 활성 여부와 v의 활성 여부가 같은 때 (즉, XOR가 false) 유효하며 역방향의 edge (v → u)는 현재 상태에서 u와 v의 활성 여부가 다를 때 (즉, XOR가 true) 유효
  • 두 케이스 모두 고려해야하므로 인접그래프를 정방향, 역방향 모두 구성 (graph, reverseGraph)

 
2. 다익스트라 알고리즘을 아래 로직과 함께 진행합니다.

• 상태 (curNode, mask)에 대해, 현재방의 함정 활성 여부(curActivated)를 확인
• 정방향 edge (graph[curNode]): 다음 방의 함정 활성 여부(nextActivated)가 현재방과 같다면 edge가 유효
• 역방향 edge (reverseGraph[curNode]): 다음 방의 함정 활성 여부가 현재방과 다르다면 edge가 유효
• 도착한 방이 함정이면 mask를 토글
• 목적지(end)에 도달하는 상태가 나오면 바로 그 비용을 반환

 

 
 
개발환경: Programmers IDE  
 
지적, 조언, 질문 환영합니다! 질문 남겨주세요~