Shortest Bridge

요즘 한참 코딩 테스트 보다 더 업무와 연관 있는 데이터 엔지니어링 지식들을 공부하다보니 코딩 능력이 많이 약해진것만 같다. 그래서 리트코드에 추천으로 나온 문제를 풀어봤는데 생각보다 많이 헤맸어서 좀 자극을 받을 필요가 있다고 생각했다 ㅠㅠ.

이 문제는 최소한의 0을 뒤집는 거로 Matrix안에 있는 두 1을 연결 시켜야하는 문제다. 어떻게 할 수 있을까??
가장 먼저 첫번째 1에 대한 연결된 모든 섬들을 연결해주고 표시해준다. 이 문제에서 나는 2로 표시했다. 그리고 두번째 룹을 돌려서 표시되지 않은 섬을 상대로 BFS를 날려서 가장 최단 거리에서 첫번째로 확인 해주었던 2로 표시된 섬과 닿는 최소 구간을 가지고 오면 끝난다.

솔직히 풀고나니 그렇게 어려운 문제는 아니고 예전에 한참 백준에서 풀던 문제와 유사 했으나 더 연습할 필요가 있을거같다.

class Solution {
    int[][] dir = {{0,1},{0,-1},{-1,0},{1,0}}; 
    class Node{
        int x, y, dist; 
        Node(int x, int y, int dist){
            this.x = x;
            this.y = y; 
            this.dist = dist; 
        }
    }
    public void dfs(int i, int j, int[][] grid){
        if(i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] != 1) return; 
        grid[i][j] = 2; 
        dfs(i+1,j,grid); 
        dfs(i-1,j,grid); 
        dfs(i,j+1,grid);
        dfs(i,j-1,grid); 
    }
    public int bfs(int i, int j, Queue<Node> q, int[][] grid){
        boolean[][] visited = new boolean[grid.length][grid[0].length]; 
        visited[i][j] = true; 
        
        while(!q.isEmpty()){
            int size = q.size(); 
            for(int k = 0; k < size; k++){
                Node first = q.poll(); 
                int x = first.x, y = first.y, dist = first.dist; 
                
                if(grid[x][y] == 2) return dist - 1; 
                
                for(int[] d : dir){
                    int nX = x + d[0]; 
                    int nY = y + d[1]; 
                    
                    if(nX < 0 || nY < 0 || nX >= grid.length || nY >= grid[0].length || visited[nX][nY] || grid[nX][nY] == 1) continue; 
                    visited[nX][nY] = true; 
                    q.add(new Node(nX,nY,dist+1)); 
                }
            }
        }
        return Integer.MAX_VALUE; 
    }
    public int shortestBridge(int[][] grid) {
        
        boolean flag = false; 
        int answer = Integer.MAX_VALUE; 
        for(int i = 0; i < grid.length; i++){
            for(int j = 0; j < grid[i].length; j++){
                if(!flag && grid[i][j] == 1){
                    dfs(i,j,grid); 
                    flag = true; 
                }
            }
            if(flag) break; 
        }
        
        for(int i = 0; i < grid.length; i++){
            for(int j = 0; j < grid[i].length; j++){
                if(grid[i][j] == 1){
                    Queue<Node> q = new LinkedList<>(); 
                    q.add(new Node(i,j,0)); 
                    answer = Math.min(answer,bfs(i,j,q,grid)); 
                }
            }
        }
        return answer; 
    }
}