LC1162. As Far from Land as Possible

작성일

https://leetcode.com/problems/as-far-from-land-as-possible/

  • 등산로 찾기에서 풀어본 DP랑 섞인 BFS문제.
  • 근데 이것도 DFS로 풀림 -_-…
  • 여튼간 오래간만에 평면 BFS를 짜본거에 의의를 두자.
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
46
47
48
49
50
51
52
class Solution {
    vector<vector<int>> dist;
public:
    struct Node {
        int x, y;
    };
    
    inline bool bound(int x) {
        return x >= 0 && x < dist.size();
    }
    
    void bfs(int x, int y) {
        const int dx[4] = {0,0,1,-1};
        const int dy[4] = {-1,1,0,0};
        
        queue<Node> q;
        q.push({x,y});
        
        int sz, d = 0;
        while(sz = q.size()) {
            d++;
            for(int i = 0; i < sz; i++) {
                Node cur = q.front(); q.pop();
                for(int j = 0; j < 4; j++) {
                    int nx = cur.x+dx[j];
                    int ny = cur.y+dy[j];
                    if(!bound(nx) || !bound(ny) || dist[nx][ny] <= d) continue;
                    
                    dist[nx][ny] = d;
                    q.push({nx,ny});
                }
            }
        }
    }
    
    int maxDistance(vector<vector<int>>& grid) {
        dist = grid;
        for(int i = 0; i < dist.size(); i++)
            for(int j = 0; j < dist[0].size(); j++)
                dist[i][j] = grid[i][j] ? -1 : 0xffff;
        
        for(int i = 0; i < dist.size(); i++)
            for(int j = 0; j < dist[0].size(); j++)
                if(grid[i][j]) bfs(i,j);
        int ans = -1;
        for(int i = 0; i < dist.size(); i++)
            for(int j = 0; j < dist[0].size(); j++)
                ans = max(ans, dist[i][j]);
        if (ans == 0xffff) return -1;
        return ans;
    }
};