[25.03.11] algo 백준 22955 리뷰

25.03.11(Tue) 알고리즘 스터디 리뷰

문제 요약

문제 개요
고양이 도도가 강아지들을 피해 탈출구까지 이동하며 체력을 최소로 소비해야 한다. 방은 다양한 상태로 구성된 격자 형태이며, 각 상태에 따라 이동 방식과 체력 소모가 다르다.

이동 조건

• 사다리(L): 위/아래로 이동 가능, 5 체력 소모.
• 아래가 뚫린 공간(X): 아래로 착지 가능, 10 체력 소모.
• 평평한 바닥(F): 좌우 이동 가능, 1 체력 소모

목표
다익스트라 알고리즘을 사용해 최소 체력으로 탈출구(E)에 도달하는 경로를 계산한다. 탈출 불가능한 경우 “dodo sad”를 출력한다.

입력
방의 크기 NxM 과 공간 상태를 나타내는 격자 정보가 주어진다. 고양이(C)와 탈출구(E)는 각각 하나씩 존재한다.

출력
최소 체력 소모량을 출력하거나 탈출 불가능 시 “dodo sad”를 반환한다.

풀이방식

다익스트라 vs bfs
처음 풀이를 시작할때는 bfs로 풀이가 가능하다고 생각했으나 이동하는 방식마다의 소모되는 체력이 달라서 최단거리를 보장할 수 없는 문제가 있었다. 그래서 priority_queue를 활용한 다익스트라 방식으로 풀이해야 했다.

시간초과??
처음 제출했을때부터 5번 정도 수정했을때 까지 시간초과를 겪었다… 결과적으로 내 힘으로 풀이를 하기에는 쉽지 않은 문제였다. 최근에 풀었던 문제중에서 다익스트라가 없기도 했고 이정도로 구현을 요구하는 문제를 오랜만에 풀이했다보니 어려움을 겪었다.
내가 풀이했던 방식과 결과적으로 맞았던 문제의 차이에는 여러가지가 있었다.

1. X 타일 처리 x 타일 처리시에 끝이 ‘D’라면 갈 필요없는 경우였는데 이 경우를 제외하지 않았다. 그리고 그 과정에서 중간에 있는 dist 값을 갱신하지 않아서 필요없는 경로가 제외되지 않았던 문제가 있었다.
2. L 타일 처리 처음에는 타일에 도착했을때 처리하는 방식으로 풀이했는데 타일을 검색할 때 위로 올라가거나 아래로 가는 것을 분할해서 생각하지 못했다. 해당 칸이 사다리 칸이거나 아래 칸이 사다리 칸인 경우로 경우의 수를 세세하게 처리하는 것이 시간을 단축시킬 수 있었다.(원래는 for문을 통해서 처리했었다.)

다익스트라 문제를 풀이할때는 경우의 수를 최대한 상세하게 나누는 것을 고려해봐야 한다.

결과 코드