되게 인상깊은 문제를 풀어봤다. BFS 문제인데 4방향으로 0이랑 가장 가까운 거리를 담는 문제다.
단순하게 BFS를 생각하기에 좀 고려해야 하는 부분이 있다. 만약에 4방향에서 0이 다 있다라면은 쉽겠지만 1이 여러번 겹쳤을때는 같은 구간을 계속 탐색 해야한다는 안좋은 조건이 있다.
그렇기 때문에 이 문제를 최적화 해서 생각하려면 조금 반대 방향으로 생각해야한다. 어떻게 하면 1만 탐색할 수 있을까? 0에서부터 시작하면 된다.
처음 탐색을 할때 0을 모두 visited 로 만들어주고 0에서부터 시작된 탐색을 하면은 가장 가까운 거리로 1을 표시해줄거라 최적화가 잘되어 문제를 풀 수 있다.
2020년에도 이 문제를 풀었는데 그때는 테스트케이스가 많지 않아서 통과됐지만 다시 풀어보니 생각을 많이 해야하는 문제다.
BFS를 풀때, 짧은 거리 문제에서 발상을 조금 다르게 생각하는것도 좋을거같다.
class Solution {
vector<pair<int,int>> dir = {{0,1},{0,-1},{1,0},{-1,0}};
struct Node{
int x, y, dist;
};
public:
vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
vector<vector<int>> matrix(mat.size(), vector<int>(mat[0].size(),0));
vector<vector<bool>> visited(mat.size(), vector<bool>(mat[0].size(), false));
queue<Node> q;
for(int i = 0; i < mat.size(); i++){
for(int j = 0; j < mat[0].size(); j++){
if(mat[i][j] == 0){
q.push({i,j,0});
visited[i][j] = true;
}
}
}
while(!q.empty()){
int size = q.size();
for(int i = 0; i < size; i++){
Node node = q.front();
q.pop();
int x = node.x, y = node.y, dist = node.dist;
for(pair<int,int>& p : dir){
int nX = x + p.first;
int nY = y + p.second;
if(nX < 0 || nY < 0 || nX >= mat.size() || nY >= mat[0].size() || visited[nX][nY]) continue;
visited[nX][nY] = true;
matrix[nX][nY] = dist + 1;
q.push({nX,nY,dist+1});
}
}
}
return matrix;
}
};