934. Shortest Bridge

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

 

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.

 

Example 1:
Input: grid = [[0,1],[1,0]]
Output: 1

Example 2:
Input: grid = [[0,1,0],[0,0,0],[0,0,1]]
Output: 2

Example 3:
Input: grid = [[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]
Output: 1

 

2차원 배열의 grid에서 1은 땅, 0은 물을 뜻한다. 배열에서는 땅이 2개로 나뉘어져 있는데 0 -> 1로 만들어 두 섬을 이을 수 있는 최솟값을 구하는 문제였다.

 

1. 배열에서 방문되지 않고, grid[i][j] = 1인 원소들을 bfs 돌린다.
2. bfs를 돌면서 인접한 모든 1을 방문처리하고, 큐에 넣어준다.
3. 첫 시작점과 인접한 1을 모두 큐에 넣었다면, break 처리를 해서 두번째 섬의 좌표는 방문하지 않아야 한다.
4. 큐에는 첫번째 섬의 좌표들만 있으므로, 좌표들을 순회하면서 방문처리 되지 않고, grid[i][j] = 1인 원소를 찾을 때 까지 다시 BFS를 돌린다. 
5. 각 큐의 노드 탐색이 끝날 때 마다, dist 값을 1씩 증가시켜준다.
6. grid[i][j] = 1인 좌표를 찾을 때, dist값을 리턴시켜준다.

 

정답 코드

class Solution {
    int n, m;
    int [] dx = {1,0,-1,0};
    int [] dy = {0,1,0,-1};

    boolean [][] visited;
    Queue<int []> firstQ = new LinkedList<>();
    Queue<int []> q = new LinkedList<>();
    public int shortestBridge(int[][] grid) {
        n = grid.length; 
        m = grid[0].length;
        visited = new boolean[n][m];

        boolean flag = false;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if (flag) break;
                if (!visited[i][j] && grid[i][j] == 1) {
                    bfs(grid, i, j);
                    System.out.println(i + " " + j);
                    flag = true;
                }
            }
        }

        int dist = 0;
        
        while(!q.isEmpty()) {
            int size = q.size();
            for(int i = 0; i < size; i++) {
                int [] cur = q.poll();
                int x = cur[0];
                int y = cur[1];

                System.out.println("cur: " + x + " " + y);

                for (int dir = 0; dir < 4; dir++) {
                    int nx = x + dx[dir];
                    int ny = y + dy[dir];

                    if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
                    if (visited[nx][ny]) continue;

                    if (grid[nx][ny] == 1) {
                        return dist;
                    }

                    visited[nx][ny] = true;
                    q.add(new int[]{nx, ny});
                }
            }
            dist++;
        }
        
        

        return 0;
    }

    public void bfs(int [][] grid, int x, int y) {
        visited[x][y] = true;
        firstQ.add(new int[]{x,y});

        while(!firstQ.isEmpty()) {
            int [] cur = firstQ.poll();
            x = cur[0];
            y = cur[1];
            q.add(new int[]{x,y});
            for(int dir = 0; dir < 4; dir++) {
                int nx = x + dx[dir];
                int ny = y + dy[dir];
                if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
                if (visited[nx][ny] || grid[nx][ny] == 0) continue;
                visited[nx][ny] = true;
                firstQ.add(new int[]{nx,ny}); 
            }
        }        
    }
}

 

 

해당 예제에서 진행 순서를 다음과 같이 그림으로 그려보면 이해가 더 잘될 것이다.

[[1, 1, 0, 0, 0],
 [1, 0, 0, 0, 0],
 [1, 0, 0, 0, 0],
 [0, 0, 0, 1, 1],
 [0, 0, 0, 1, 1]]

 

# 첫번째 진행
0 0 1 0 0 
0 1 0 0 0 
0 1 0 0 0 
1 0 0 0 0 
0 0 0 0 0 

# 두번째 진행
0 0 1 2 0 
0 1 2 0 0 
0 1 2 0 0 
1 2 0 0 0 
2 0 0 0 0 

# 세번째 진행
0 0 1 2 3 
0 1 2 3 0 
0 1 2 3 0 
1 2 3 0 0 
2 3 0 0 0

 

이렇게 첫번째 섬에서 부터 거리값을 하나씩 증가시켜 나가고, 섬에 도달할 때 까지의 거리값을 계산해주면 된다. 

단, 섬에 도달했을 때의 거리는 포함하지 않으므로 정답은 3이된다. 

 

 

좌표들을 전부 저장하고 한번에 BFS를 돌리는게 살짝 이해가 되지 않았는데 하나씩 출력해보니 이해가 되었다.