2024년부터 새롭게 다시 시작하는 코딩테스트
2024년 5월 15일 (수)
Leetcode daily problem
2812. Find the Safest Path in a Grid
Problem
n x n 크기의 0 인덱스 2D 매트릭스 grid가 제공될 때, 여기서 (r, c)는
- grid[r][c] = 1인 경우 도둑이 포함된 셀
- grid[r][c] = 0인 경우 빈 셀
이다.
처음에는 셀 (0, 0)에 위치하고, 한 번의 이동으로 도둑이 있는 셀을 포함하여 그리드의 인접한 셀로 이동할 수 있다.
그리드에 있는 경로의 안전 계수는 경로에 있는 셀에서 grid에 있는 도둑까지의 최소 맨해튼 거리로 정의된다.
cell(n - 1, n - 1)로 이어지는 모든 경로의 최대 안전 인자를 반환하는 것이다.
- cell (r, c)의 인접한 셀은 (r, c + 1), (r, c - 1), (r + 1, c) 및 (r - 1, c) 중 하나이다.
두 셀 (a, b)와 (x, y) 사이의 맨해튼 거리는 |a - x|+ |b - y| 이고, 여기서 |val| Val의 절대값을 나타냅니다.
Solution
BFS + 다익스트라 알고리즘 변형
n x n 크기의 격자에서 시작 지점 (0, 0)에서 끝 지점 (n-1, n-1)까지 도달하는 경로의 "최대 안전 계수"를 찾는 문제이다.
Code
Complexicity
시간 복잡도
distances 배열을 초기화 하는데 O(n^2)의 시간이 소요되고, 정해진 위치를 찾기 위해 이중 반복문을 통해 grid를 탐색하므로 O(n^2)이 소요된다.
bfs 알고리즘은 각 노드를 한 번씩 방문하고 네 방향으로 이동을 시도해서 O(n^2)이 또 소요된다.
추후에 안전 거리를 계산하기 위해서 우선순위 큐에서 첫 번째 노드를 삽입 하고 O(1), 우선순위 큐를 이용해서 다익스트라 알고리즘은 모든 노드를 방문하면서 네 방향으로 이동을 시도하므로 큐에서 한번 꺼낼 때 O(log(n^2)) 시간이 소요된다.
총 노드의 수가 n^2이고 각 노드를 큐에 삽입하고 꺼내는 작업을 반복하므로 O(n^2log(n^2)) = O(n^2 log(n)) 시간이 소요된다.
즉, 전체적인 시간 복잡도는 O(n^2) + O(n^2log(n)) 으로 O(n^2 log(n)) 이다.
공간 복잡도
distance 배열의 크기가 O(n^2) 이고, bfs를 수행하기 위한 큐의 최대 크기도 O(n^2) 이다. 안전거리를 계산하기 위한 배열과 큐의 크기 또한 O(n^2) 이라 전체 공간복잡도는 O(n^2) 이다.
이게 어떻게... medium이지 hard 아닌가..?
