[BJ] 13460 - 구슬 탈출 2

안녕하세요, Einere입니다.

(ADblock을 꺼주시면 감사하겠습니다.)

---

이번 포스트에서는 백준 13460번 문제인 구슬 탈출 2에 대해 알아보도록 하겠습니다.

 

회의 날자 : 2019.10.13

회의 장소 : 패스트파이브 서울숲점 2A

 

접근 방법

구슬을 최대한 적은 횟수로 기울여서 탈출시켜야 합니다. 딱 봐도 감이 오시나요? BFS를 사용하는 문제랍니다.

 

제가 생각한 이 문제의 키 포인트들입니다.

• 트리 구조 : 판을 상하좌우 4방향으로 기울일 수 있습니다. 다음 상태는 이전의 상태와 수행한 동작에 영향을 받으므로, 각 상태를 트리의 노드로 생각할 수 있습니다.
• BFS : 트리 구조에서, 최단 횟수를 구하는 경우에 사용합니다. BFS는 해를 찾았을 경우 해당 해가 최단거리임을 보장하지만, DFS는 최단 거리를 보장하지 못하기 때문이죠.
• queue: BFS를 사용한다면 당연히 따라오는 큐입니다.
• depth limit : 그래프의 정점 탐색과는 다르게, 이 문제는 어마무시하게 많은 상태가 존재합니다. 왼쪽으로 기울였다 위쪽으로 기울인 상태와 위쪽으로 기울인 후 왼쪽으로 기울인 상태는 우연의 일치로 같을 수 있지만, 왠만하면 다른 상태일 것입니다. 따라서 엄청나게 깊은 곳에 해가 존재할 수 있기 때문에, 문제에서도 최대 10회까지만 탐색하라고 키워드를 줬습니다.
• 뻘짓 피하기 : 왼쪽으로 기울인 후 오른쪽으로 기울이는 것은 원래 상태로 되돌아가는 동작입니다. 또한 같은 방향으로 계속해서 기울이는 것 또한 동일한 경우입니다. 따라서, queue와 visited를 이용해 이런 뻘짓을 방지해야 합니다.
• 움직이는 순서 : 문제에서는 빨간 구슬과 파란 구슬 두개가 존재합니다. 특정 방향으로 기울였을 때, 해당 방향에 가까운 구슬을 먼저 움직여 줘야 다른 구슬이 제대로 이동할 수 있습니다.
• visited : 뻘짓을 피하기 위해서는 이때까지 수행한 동작을 기록해야 할 필요가 있습니다. 이전의 상태와 동작 후의 상태가 다른 경우일 경우에만 기록을 하면 될 것 같습니다.
• 이전 상태의 전달 : 한 상태에서 기울이기를 해서 자식 상태로 넘어가고자 한다면, 현재 상태를 같이 넘겨줘야 합니다. 동작 후의 상태를 구하기 위해서는 넘겨받은 상태를 깊은 복사해서 사용해야 합니다.

대충 생각해도 어마어마하게 많은 제약조건들이 있네요. 괜히 정답률이 20%대인게 아니네요.

 

 

개선점

• 갈 수 잇는 곳을 미리 확인한 후, queue에 방향을 넣기.
• depth대신 visited.length를 활용하기.
• visited에 방향 외에도 상태도 같이 저장하자.
• 맵을 입력 받을때 공 위치는 .으로 치환하자.

 

 

풀이 코드(java script)

풀지도 못했거니와.. 너무 더러워서 공개하기 부끄럽네요.