LeetCode (C/C++) 542. 01 Matrix

https://leetcode.com/problems/01-matrix/description/

---

풀이

0과 맞닿아 있는 1부터 탐색을 시작해야 한다.

그 조건을 어떻게 구현해야 할지 모르겠어서 힌트를 확인했고, 0인 위치를 저장 후 해당 값부터 bfs를 실행하면 된다는 걸 알았다.

그 후부터는 bfs를 실행하며 현재 위치의 입력이 1이라면 탐색 시 값을 갱신해주었다.

 

visited[][] 선언 시 m, n의 값이 각 10000으로 배열의 크기가 10000 * 10000 이 되어 선언할 수 없다.

그래서 vector로 선언 후 resize() 해주었는데, 다른 풀이를 보니 visited[] 선언 없이 풀길래 해당 방법으로도 풀어보았다.

---

코드 1

class Solution {
public:
    queue<pair<int, int>> q;
    vector<vector<bool>> visited;

    // bfs
    void bfs(vector<vector<int>>& mat, int row, int col) {
        int mx[4] = {0, 0, 1, -1}, my[4] = {-1, 1, 0, 0};

        while (!q.empty()) {
            auto now = q.front();
            q.pop();

            for (int i = 0; i < 4; i++) {
                int nx = now.first + mx[i], ny = now.second + my[i];
                if (nx < 0 || row <= nx || ny < 0 || col <= ny || visited[nx][ny]) continue;

                if (mat[nx][ny]){
                    mat[nx][ny] = mat[now.first][now.second] + 1;
                    visited[nx][ny] = true;
                    q.push({nx, ny});
                }
            }
        }
    }

    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        int row = mat.size(), col = mat[0].size();
        visited.resize(row, vector<bool>(col, false));

        // 0인 위치만 저장 및 방문 표시
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (mat[i][j]) continue;
                
                q.push({i, j});
                visited[i][j] = true;
            }
        }
        bfs(mat, row, col);
        return mat;
    }
};

 

코드 2

class Solution {
public:
    queue<pair<int, int>> q;
    
    // bfs
    void bfs(vector<vector<int>>& mat, int row, int col) {
        int mx[4] = {0, 0, 1, -1}, my[4] = {-1, 1, 0, 0};

        while (!q.empty()) {
            auto now = q.front();
            q.pop();

            for (int i = 0; i < 4; i++) {
                int nx = now.first + mx[i], ny = now.second + my[i];
                if (nx < 0 || row <= nx || ny < 0 || col <= ny || mat[nx][ny] != -1) continue;

                mat[nx][ny] = mat[now.first][now.second] + 1;
                q.push({nx, ny});
            }
        }
    }

    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        int row = mat.size(), col = mat[0].size();

        // visited[] 대신 방문한 적 없는 노드 값 -1로 채움
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (mat[i][j])
                    mat[i][j] = -1;
                else
                    q.push({i, j});
            }
        }
        bfs(mat, row, col);
        return mat;
    }
};