Leetcode 286) Walls and Gates

30 Jul 2021 in Algorithms

내 답안

• gate를 queue에 넣어서 동시에 해결

class Solution {
    public void wallsAndGates(int[][] rooms) {
        Queue<int[]> q= new LinkedList<>();
        for(int i =0;i<rooms.length;i++){    
            for(int j =0;j<rooms[0].length;j++){
                if(rooms[i][j]==0){
                    q.add(new int[]{i,j});
                }

            }
        }
        int cnt=0;
        while(!q.isEmpty()){
            cnt++;
            int size = q.size();
            //size를 앞에서 저렇게 해야지, 안그면은 계속 늘어나서 곤란해진다.
            for(int i =0;i<size;i++){
                int[] ind=q.poll();
                if(ind[0]+1<rooms.length){
                    if(rooms[ind[0]+1][ind[1]]>cnt){
                        rooms[ind[0]+1][ind[1]]=cnt;
                        q.add(new int[]{ind[0]+1,ind[1]});}
                }
                if(ind[0]-1>=0){
                    if(rooms[ind[0]-1][ind[1]]>cnt){
                        rooms[ind[0]-1][ind[1]]= cnt;
                        q.add(new int[]{ind[0]-1,ind[1]});}
                }
                if(ind[1]-1>=0){
                    if(rooms[ind[0]][ind[1]-1]>cnt){
                        rooms[ind[0]][ind[1]-1]=cnt;
                        q.add(new int[]{ind[0],ind[1]-1});}
                }
                if(ind[1]+1<rooms[0].length){
                    if(rooms[ind[0]][ind[1]+1]>cnt){
                        rooms[ind[0]][ind[1]+1]=cnt;
                        q.add(new int[]{ind[0],ind[1]+1});
                    }
                }}

        }
    }
}

다른 답안

class Solution {
    public void wallsAndGates(int[][] rooms) {
        for(int i = 0; i < rooms.length; i++)
        {
            for(int j = 0; j < rooms[i].length; j++)
            {
                if(rooms[i][j] == 0)
                {
                    dfs(i, j, 0, rooms);
                }
            }
        }
    }

    public void dfs(int i, int j, int count, int[][] rooms)
    {
        if(i < 0 || i >= rooms.length || j < 0 || j >= rooms[i].length || rooms[i][j] < count)
        {
            return;
        }

        rooms[i][j] = count;

        if(i < rooms.length - 1 && count+1 < rooms[i+1][j]){
            dfs(i+1, j, count+1, rooms);
        }
        if(i > 0 && count+1 < rooms[i-1][j]){
            dfs(i-1, j, count+1, rooms);
        }
        if(j < rooms[i].length-1 && count+1 < rooms[i][j+1]){
            dfs(i, j+1, count+1, rooms);
        }
        if(j > 0 && count+1 < rooms[i][j-1]){
            dfs(i, j-1, count+1, rooms);
        }
    }
}