5558. チーズ (Cheese)#

관찰#

문제는 주어진 격자 그래프에서
시작 지점 $$ S $$ 에서 시작해서 1부터 $$ N $$ 까지 순서대로 방문할 때,
최소 이동 비용을 구하는 것이다.

각 치즈는 순서대로 먹어야 하므로,
현재 위치에서 다음 목표 치즈까지의 최단 거리를 반복해서 구하는 문제로 환원할 수 있다.

격자는 가중치가 없는 그래프이기 때문에,
각 구간의 최단 거리는 BFS로 구하는 것이 가장 직관적이라 판단했고,
이를 기반으로 풀이를 구성했다.

문제의 조건은
$1 \le H \le 1{,}000$ , $1 \le W \le 1{,}000$ , $1 \le N \le 9$ 이다.

격자 전체에 대해 BFS를 한 번 수행하는데
$O(H \cdot W)$ 의 시간이 걸리고,

N번의 BFS를 수행하면 총 $O(N \cdot H \cdot W)$ 의 시간복잡도가 발생한다.

최대값을 대입하면 $1000 \cdot 1000 \cdot 9 \approx 9{,}000{,}000$ 으로,
1초 제한 내에 충분히 풀이가 가능하다.

초기 코드 구성은
한 BFS함수 내에서 재귀적으로 1부터 $$ N $$ 까지 탐색하는 코드를 구성했다.

하지만 이 경우

으로 인해, 불필요한 메모리 할당 비용과 초기화 비용이 발생했다.

첫 번째 개선 사항으로, visit배열을 BFS함수 외부에서 한 번만 생성하고,
각 BFS마다 재사용하는 방식으로 변경했다.

하지만 단순히 거리를 저장하는 배열로 사용할 경우,
매 BFS마다 전체 배열을 초기화해야 하므로 시간 오버헤드는 여전히 남아 있었다.

이를 위해 visit에는 방문 여부만, 거리 정보는 BFS 노드 내로 분리하여 코드를 구성했다.

이를 통해 visit 배열에는 현재 몇 번째 치즈를 탐색 중인지를 마킹하는 방식으로 값을 기록하여,
배열을 매번 초기화하지 않고도 재사용할 수 있도록 했다.

이를 통해

를 모두 달성했다.

현재 2025-01-10 기준, 코드는 Python3 기준 가장 빠른 코드이다.