[Grind75-LeetCode] 01 Matrix - Medium
접근
- bfs
- dp
풀이
0과 1로 이루어진 2차원 배열을 통해 각 인덱스에서 제일 가까운 0까지의 거리가 얼마나 되는지 구하는 문제이다. 문제를 보니 늘 사용하던 bfs를 통해 풀면 될 거 같은 문제였다.
private static final int[] dx = {0, 0, -1, 1};
private static final int[] dy = {1, -1, 0, 0};
public int[][] updateMatrix(int[][] mat) {
int[][] res = new int[mat.length][mat[0].length];
Queue<int[]> que = new LinkedList<>();
for (int i = 0; i < res.length; i++) {
for (int j = 0; j < res[i].length; j++) {
if (mat[i][j] == 0) {
que.offer(new int[]{i, j});
} else {
res[i][j] = Integer.MAX_VALUE;
}
}
}
bfs(que, res);
return res;큐를 사용할 것이고 인덱스 값이 1인 곳에서 0까지의 거리를 탐색하는 것이 아닌 0에서 인덱스 값이 1이 나올 때까지 탐색을 진행하도록 했다. 그러기 위해 2차원 배열을 순회하며 값이 0일 때 큐에 시작점으로 추가하고 값이 1이라면 결과 배열을 무한대로 초기화했다.
public void bfs(Queue<int[]> que ,int[][] res) {
while (!que.isEmpty()) {
int[] xy = que.poll();
int x = xy[0];
int y = xy[1];
for (int d = 0; d < 4; d++) {
int nx = xy[0] + dx[d];
int ny = xy[1] + dy[d];
if (nx < 0 || nx >= res.length || ny < 0 || ny >= res[nx].length) {
continue;
}
if (res[nx][ny] > res[x][y] + 1) {
res[nx][ny] = res[x][y] + 1;
que.offer(new int[]{nx, ny});
}
}
}
}bfs 메서드로 시작점이 들어있는 큐와 mat 배열을 파라미터로 받는다. 이번에는 방문체크를 사용하지 않았는데 dp와 유사한 방식으로 이전 인덱스에서 + 1로 한 칸을 더 진행한 값이 다음 목적지 인덱스의 값 보다 작다면 그것이 최단 거리이므로 업데이트해 나가는 방식이다.
반복이 많이 일어나긴 하지만 이런 최단 거리를 구하는 문제에 늘 bfs를 써왔기 때문에 성능이 좋은 방법이라고 생각하고 있었다.
그러나 하위 16.72% 의 성능으로 처참한 결과가 나왔다. 그래서 다른 사람의 풀이를 보던 중 99% Beats가 나오는 코드가 있어 해당 코드를 들고 와 분석을 해보려고 한다.
priyanshu1078라는 사람이 올려둔 코드로 DP를 사용한 방식으로 풀어졌다. 우선 이 코드의 풀이 방식은 상하좌우 방향을 두 가지 메서드로 분리해 왼쪽과 위쪽 방향을 먼저 계산하고 아래쪽과 오른쪽 방향을 계산해 최소 거리를 구하는 방법이다.
public int[][] updateMatrix(int[][] mat) {
int m = mat.length;
int n = mat[0].length;
//위쪽과 왼쪽에서 거리 계산
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// 현재 인덱스 값이 1인 경우
if (mat[i][j] == 1) {
// 위쪽과 왼쪽에서의 최소 거리를 찾아 업데이트
mat[i][j] = sol1(mat, i, j);
}
}
}
//아래쪽과 오른쪽에서 거리 계산
for (int i = m - 1; i >= 0; i--) {
for (int j = n - 1; j >= 0; j--) {
// 현재 인덱스 값과 아래쪽, 오른쪽에서의 최소 거리 비교
mat[i][j] = Math.min(mat[i][j], sol2(mat, i, j));
}
}
return mat;
}위쪽과 왼쪽에서 먼저 최소 거리를 찾은 뒤 오른쪽과 아래쪽을 탐색하며 최소 거리를 찾는다. 왼쪽과 위쪽의 경우 0부터 정방향 탐색을 진행하는데 현재 인덱스 값이 1인 경우에만 진행하게 된다. 오른쪽과 아래쪽의 경우 모든 인덱스에 인덱스의 마지막 값부터 역방향 탐색을 진행해 다시 한번 최적의 거리를 탐색한다.
public int sol1(int[][] mat, int r, int c) {
int ans = mat.length * mat[0].length; // 가능한 최대 거리로 초기화
// 위쪽 인덱스 값 확인
if (r > 0) ans = Math.min(mat[r - 1][c], ans);
// 왼쪽 인덱스 값 확인
if (c > 0) ans = Math.min(mat[r][c - 1], ans);
return ans + 1; // 최소 거리 + 1 (현재 인덱스 값 포함)
}먼저 왼쪽과 위쪽을 탐색하는 메서드이다. 거리를 최대로 초기화 한 뒤 위쪽과 아래쪽을 확인하며 최단 거리로 변경한다. 현재 인덱스 값이 1인경우 실행되는 메서드이기 때문에 왼쪽과 위쪽에 0이 있다면 인덱스 값에 1을 더한 값으로 변경될 것이고 그렇지 않다면 최대거리를 유지하게 된다.
public int sol2(int[][] mat, int r, int c) {
int ans = mat.length * mat[0].length; // 가능한 최대 거리로 초기화
// 아래쪽 인덱스 값 확인
if (r < mat.length - 1) ans = Math.min(mat[r + 1][c], ans);
// 오른쪽 인덱스 값 확인
if (c < mat[0].length - 1) ans = Math.min(mat[r][c + 1], ans);
return ans + 1; // 최소 거리 + 1 (현재 인덱스 값 포함)
}오른쪽과 아래쪽을 탐색하는 메서드이다. 조건의 범위가 변경되었을 뿐 수행 내용은 똑같다. 이 메서드를 수행하며 아래쪽과 오른쪽에 0이 있는 경우 최대 거리를 유지하던 인덱스가 오른쪽과 아래쪽의 탐색으로 값이 변경된다.
두 코드의 수행시간은 5ms와 19ms로 거의 4배에 가까운 차이가 나지만 실제로 시간 복잡도는 동일하다. 5ms 의 수행시간을 가진 저 코드도 O(m x n) + O(m x n) = O(m x n)이고 첫 번째 bfs를 사용한 코드 또한 모든 인덱스를 순회하는데 O(m x n) 그리고 최악의 경우 모든 인덱스를 큐에서 꺼내고 각 4방향을 체크하기 때문에 O(m x n)으로 O(m x n) + O(m x n) = O(m x n)으로 시간 복잡도는 동일하다.
그렇다면 O(m x n)으로 같은 시간 복잡도를 가지면서 왜 수행 시간이 4배 가량 차이가 나나? 5ms의 코드는 단순한 배열을 통한 계산이 주로 이루어져 상대적으로 빠른 시간에 수행이 가능하고 bfs 코드의 경우 Queue를 사용한 연산이 반복적으로 많이 발생하기 때문에 그만큼의 오버헤드가 추가로 발생하여 생기는 문제라고 볼 수 있을 거 같다. 추가적으로 배열을 사용한 코드의 경우 배열의 인덱스에 대한 접근이 일정한 패턴을 이루므로 CPU 캐시를 효과적으로 활용할 수 있다. 그러나 Queue를 사용할 경우 이웃 인덱스에 대한 접근이 불규칙 해 CPU 캐시 활용이 효과적이지 않을 가능성이 높다.
전체 코드
BFS
class Solution {
private static final int[] dx = {0, 0, -1, 1};
private static final int[] dy = {1, -1, 0, 0};
public int[][] updateMatrix(int[][] mat) {
int[][] res = new int[mat.length][mat[0].length];
Queue<int[]> que = new LinkedList<>();
for (int i = 0; i < res.length; i++) {
for (int j = 0; j < res[i].length; j++) {
if (mat[i][j] == 0) {
res[i][j] = 0;
que.offer(new int[]{i, j});
} else {
res[i][j] = Integer.MAX_VALUE;
}
}
}
bfs(que, res);
return res;
}
public void bfs(Queue<int[]> que ,int[][] res) {
while (!que.isEmpty()) {
int[] xy = que.poll();
int x = xy[0];
int y = xy[1];
for (int d = 0; d < 4; d++) {
int nx = xy[0] + dx[d];
int ny = xy[1] + dy[d];
if (nx < 0 || nx >= res.length || ny < 0 || ny >= res[nx].length) {
continue;
}
if (res[nx][ny] > res[x][y] + 1) {
res[nx][ny] = res[x][y] + 1;
que.offer(new int[]{nx, ny});
}
}
}
}
}
배열
class Solution {
public int[][] updateMatrix(int[][] mat) {
int m=mat.length;
int n=mat[0].length;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(mat[i][j]==1){
mat[i][j]=sol1(mat,i,j);
}
}
}
for(int i=m-1;i>=0;i--){
for(int j=n-1;j>=0;j--){
mat[i][j]=Math.min(mat[i][j],sol2(mat,i,j));
}
}
return mat;
}
public int sol1(int[][] mat,int r,int c){
int ans=mat.length*mat[0].length;
if(r>0) ans=Math.min(mat[r-1][c],ans);
if(c>0) ans=Math.min(mat[r][c-1],ans);
return ans+1;
}
public int sol2(int[][] mat,int r,int c){
int ans=mat.length*mat[0].length;
if(r<mat.length-1) ans=Math.min(mat[r+1][c],ans);
if(c<mat[0].length-1) ans=Math.min(mat[r][c+1],ans);
return ans+1;
}
}같은 시간 복잡도를 가진다 해도 구현을 위해 사용하는 자료구조에 따라 추가적인 비용이 발생할 수 있고 그것이 큰 차이를 가져올 수 있는걸 알게 된 거 같다.
코드 출처: 01 Matrix - LeetCode
'알고리즘 > 코딩테스트-Grind75' 카테고리의 다른 글
| [Grind75-LeetCode] Longest Substring Without Repeating Characters JAVA (1) | 2024.10.18 |
|---|---|
| [Grind75-LeetCode] K Closest Points to Origin JAVA (0) | 2024.10.17 |
| [Grind75-LeetCode] Insert Interval JAVA (0) | 2024.10.15 |
| [Grind75-LeetCode] Maximum Subarray JAVA (0) | 2024.10.14 |
| [Grind75-LeetCode] Middle of the Linked List JAVA (2) | 2024.10.13 |