[LeetCode] 934. Shortest Bridge

https://leetcode.com/problems/shortest-bridge/description/

Shortest Bridge - LeetCode

문제 유형 : DFS / BFS

문제 난이도 : Medium

 

문제

You are given an n x n binary matrix grid where 1 represents land and 0 represents water.

An island is a 4-directionally connected group of 1's not connected to any other 1's. There are exactly two islands in grid.

You may change 0's to 1's to connect the two islands to form one island.

Return the smallest number of 0's you must flip to connect the two islands.

 

n*n의 크기의 2차원 배열을 받는다. 0은 물이고, 1은 땅이다. 두 섬이 존재하는데, 하나의 섬으로 합치기 위해 0을 1로 바꿀 수 있다.

최소한으로 필요한 거리를 구하여라.

 

풀이

dfs를 이용하여 첫번째 섬을 찾아준다. 첫 번째 섬을 찾고 나서는 bfs로상하좌우를 넓혀주면서 거리도 1씩 늘린다. 첫번째 섬과 두번째 섬이 닿으면 마친다.

 

 

 

코드(C++)

class Solution {
public:
    const int dx[4] = {1, -1, 0, 0};
    const int dy[4] = {0, 0, 1, -1};

    int shortestBridge(vector<vector<int>>& grid) {
        int n = grid.size();
        
        vector<vector<bool>> visited(n, vector<bool>(n, false));
        
        queue<pair<int, int>> q;
        
        bool found = false;
        for (int i = 0; i < n; i++) {
            if (found)
                break;
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    dfs(grid, i, j, q, visited);
                    found = true;
                    break;
                }
            }
        }
        
        int distance = 0;
        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                int x = q.front().first;
                int y = q.front().second;
                q.pop();
                
                for (int j = 0; j < 4; j++) {
                    int nx = x + dx[j];
                    int ny = y + dy[j];
                    
                    if (nx >= 0 && ny >= 0 && nx < n && ny < n && !visited[nx][ny]) {
                        if (grid[nx][ny] == 1) {
                            return distance;
                        }
                        visited[nx][ny] = true;
                        q.push({nx, ny});
                    }
                }
            }
            distance++;
        }
        
        return -1; 
    }
    
    void dfs(vector<vector<int>>& grid, int x, int y, queue<pair<int, int>>& q, vector<vector<bool>>& visited) {
        if (x < 0 || y < 0 || x >= grid.size() || y >= grid[0].size() || visited[x][y] || grid[x][y] == 0)
            return;
        
        visited[x][y] = true;
        q.push({x, y});
        
        for(int i = 0; i < 4; i++){
            const int nx = x + dx[i];
            const int ny = y + dy[i];
            dfs(grid, nx, ny, q, visited);
        }
    }
};