[2021 카카오 채용연계형 인턴십] Q4. 미로 탈출 (C++, Python, Java)

문제 링크

https://programmers.co.kr/learn/courses/30/lessons/81304

 

예상 난이도

P5

 

알고리즘 분류

다익스트라, 비트마스크

 

풀이

그래프에서의 최단 경로 문제이기에 다익스트라나 플로이드가 쓰일 것으로 유추할 수 있으나 함정의 존재로 인해 그래프의 모양이 계속 달라지는 점이 껄끄럽습니다. 여기서 어떤 관찰을 필요로 하냐면, 함정은 최대 10개이기 때문에 가능한 함정의 on/off 상태는 최대 2¹⁰개임을 알아차려야 합니다.

 

다익스트라를 생각해보면, 저희는 보통 d[1...n] 테이블을 가지고 다익스트라를 돌렸지만 이번에는 함정의 상태를 감안해 d[1...n][state] 테이블을 가지고 다익스트라를 돌려야 합니다. 이 state는 각 함정 방의 on/off 상태를 비트에 대응시켜서 나타낸 값으로, 비트마스크를 모르면 이해가 아마 힘들 것으로 보입니다. 우선 주어진 그래프로 예를 들면 위의 그림과 같습니다.

 

상태까지 고려했을 때 d[1][00]은 d[2][01]로 전파가 이루어집니다. 2번 방에 도달하는 순간 2번 방이 on되기 때문입니다.

 

나머지 방들도 이렇게 상태를 감안한 간선을 다 연결할 수 있습니다.

 

이후 다익스트라를 이용해 정점과 간선이 최대 1024배 늘어난 그래프에서 d[en][...]으로의 최단 거리를 구하면 됩니다. 저는 구현을 할 때 실제로 각 state에 대응되는 정점을 다 만들어놓는 대신 매번 state를 계산하는 방식으로 구현을 했고, 주석을 나름 친절하게 달려고 노력했으니 자세한건 코드를 확인해주세요.

 

코드(C++)

 

코드(Python)

 

코드(Java)

 

관련 강의

0x1E강 - 다익스트라 알고리즘