01 Matrix

각 블록에서 가장 가까운 0을 찾는 문제.
자신이 0이면 그 블록에 값은 0이고, 옆에 있으면 1이 됨. 블록은 상하좌우로만 움직임.

처음 문제를 봤을 때 구현 문제가 생각났음.
처음 블록에서 주변 상하좌우를 확인한 후,

없으면 상,하,좌,우 이동한다. 그 다음에 다시 상,하,좌,우에 0이 있나 확인.
접근 방법은 생각났는데 코드 구현을 못해서 계속 헤메다가 BFS가 떠올라서 BFS 검색해서 어설프게 구현했음.
제일 헤멨던 게 x,y좌표 구분에서 엄청 헤멨음. x,y를 명확하게 뭐라고 확실히 정하고 하지 않아서 굉장히 고생함.
다음에 좌표 문제가 나오면 x,y 확실히 정하고 풀어야겠음.

다음엔 밑에 2가지를 신경 써서 풀어야겠음.

1. BFS 제대로 구현

2.x,y 좌표 명확하게 잡기.

푼 거.

import java.util.*;
class Node {
    int x;
    int y;
    int depth;
    Node(int x, int y, int depth) {
        this.x = x;
        this.y = y;
        this.depth = depth;
    }
}
class Solution {
    public int[][] updateMatrix(int[][] matrix) {
        List<int[]> list = new ArrayList<>();
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if (matrix[i][j] == 0) {
                    continue;
                } else {
                    //0이 아닌 애들만 모아서 리스트에 넣어줌.
                    list.add(new int[]{i,j});
                }
            }
        }
        //xWay, yWay는 상,우,하,좌 시계 방향 벡터를 나타냄. 
        //지금 생각하면 2차원 배열에 한 번에 담는 게 낫지 않았나 싶다.
        int[] xWay = new int[]{0,1,0,-1};
        int[] yWay = new int[]{-1,0,1,0};
        //자기가 0인 애들을 제외하고 최소 거리를 구해줌.
        for (int[] arr : list) {    //arr{y,x}
            Queue<Node> queue = new LinkedList();
            queue.offer(new Node(arr[1],arr[0],0));
            while (!queue.isEmpty()) {
                Node node = queue.poll();

                //if문은 상하좌우 움직였을 때. 배열 밖으로 나가지 않게 조건을 검.
                if (0 <= node.x+xWay[0] && node.x + xWay[0] < matrix[0].length  && 0 <= node.y + yWay[0] && node.y + yWay[0] <matrix.length) {
                    //이동한 좌표에 값이 0이면 반복문 종료하고 들어간 depth(이동거리)를 대입해줌.
                    if (matrix[node.y+yWay[0]][node.x + xWay[0]] == 0) {
                        matrix[arr[0]][arr[1]] = node.depth+1;
                        break;
                    }
                    //0이 아니면 queue에 넘어서 다시 그 좌표에서 상하좌우 움직이게 함.
                    queue.offer(new Node(node.x + xWay[0],node.y + yWay[0],node.depth+1));
                }
                if (0 <= node.x+xWay[1] && node.x + xWay[1] < matrix[0].length  && 0 <= node.y + yWay[1] && node.y + yWay[1] <matrix.length) {
                    if (matrix[node.y+yWay[1]][node.x + xWay[1]] == 0) {
                        matrix[arr[0]][arr[1]] = node.depth+1;
                        break;
                    }
                    queue.offer(new Node(node.x + xWay[1],node.y + yWay[1],node.depth+1));
                }
                if (0 <= node.x+xWay[2] && node.x + xWay[2] < matrix[0].length  && 0 <= node.y + yWay[2] && node.y + yWay[2] <matrix.length) {
                    if (matrix[node.y+yWay[2]][node.x + xWay[2]] == 0) {
                        matrix[arr[0]][arr[1]] = node.depth+1;
                        break;
                    }
                    queue.offer(new Node(node.x + xWay[2],node.y + yWay[2],node.depth+1));
                }
                if (0 <= node.x+xWay[3] && node.x + xWay[3] < matrix[0].length  && 0 <= node.y + yWay[3] && node.y + yWay[3] <matrix.length) {
                    if (matrix[node.y+yWay[3]][node.x + xWay[3]] == 0) {
                        matrix[arr[0]][arr[1]] = node.depth+1;
                        break;
                    }
                    queue.offer(new Node(node.x + xWay[3],node.y + yWay[3],node.depth+1));
                }
            }
        }

        return matrix;
    }
}

내가 푼 코드에 문제점이 오른쪽으로 이동했다가 다시 왼쪽으로 이동한 경우, 제자리로 돌아와서 의미가 없습니다.
그러나 위에 코드에선 해당 경우까지 처리해줍니다.
BFS 구현 하는 사람들 보면 대부분 방문한 경우를 boolean의 배열로 체크하던데 이거 때문인 듯 싶다.
BFS 다시 만들어보면서 위 코드 수정해보자.

리트코드 모법 답안

public class Solution {
    public int[][] updateMatrix(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;

        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    queue.offer(new int[] {i, j});
                }
                else {
                    matrix[i][j] = Integer.MAX_VALUE;
                }
            }
        }

        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            for (int[] d : dirs) {
                int r = cell[0] + d[0];
                int c = cell[1] + d[1];
                if (r < 0 || r >= m || c < 0 || c >= n || 
                    matrix[r][c] <= matrix[cell[0]][cell[1]] + 1) continue;
                queue.add(new int[] {r, c});
                matrix[r][c] = matrix[cell[0]][cell[1]] + 1;
            }
        }

        return matrix;
    }
}