[LeetCode] Grind 75 questions (27/75) 01 Matrix

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

class Solution {
public int[][] updateMatrix(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        int[][] distances = new int[m][n];
        Queue<int[]> queue = new LinkedList<>();
        
        // 모든 셀을 무한대로 초기화하고 0인 셀을 큐에 추가
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 0) {
                    distances[i][j] = 0;
                    queue.add(new int[]{i, j});
                } else {
                    distances[i][j] = Integer.MAX_VALUE;
                }
            }
        }
        
        // BFS를 위한 방향 배열
        int[][] directions = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };
        
        // BFS 탐색
        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            int x = cell[0];
            int y = cell[1];
            
            for (int[] dir : directions) {
                int newX = x + dir[0];
                int newY = y + dir[1];
                
                // 유효한 범위 내에 있고, 더 짧은 거리를 발견한 경우 업데이트
                if (newX >= 0 && newX < m && newY >= 0 && newY < n) {
                    if (distances[newX][newY] > distances[x][y] + 1) {
                        distances[newX][newY] = distances[x][y] + 1;
                        queue.add(new int[]{newX, newY});
                    }
                }
            }
        }
        
        return distances;
    }
}