Leetcode 296) Best Meeting Point

06 Aug 2021 in Algorithms

내 답안

다른 답안

오답

• 이런 식으로 하면 dfs가 된다. recursion으로 어케 bfs 구현하지?

class Solution {
    //317문제와는 다르게, 안가는 곳은 없으니까 세명다 닿을 수 있는 거리인지는 생각하지 않아도 된다.어차피 다 갈 수 있다.
    public int minTotalDistance(int[][] grid) {
        int[][] distant = new int[grid.length][grid[0].length];
        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[0].length;j++){
                if(grid[i][j]==1){
                    boolean[][] visited = new boolean[grid.length][grid[0].length];
                    visited[i][j]=true;
                    distant = dfs(i,j,distant,0,visited);
                }
            }
        }
        int min= Integer.MAX_VALUE;
        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[0].length;j++){
                min= Math.min(distant[i][j],min);
            }}
        return min;
    }
    
    public int[][] dfs(int i, int j , int[][] distant, int d, boolean[][] visited){
        int[][] position ={{1,0},{-1,0},{0,-1},{0,1}};
        d++;
        for (int[] ind : position){
            int a= ind[0]+i;
            int b= ind[1]+j;
            if(!(a<0 || a>= distant.length || b<0 || b>=distant[0].length)){
                if(!visited[a][b]){
                    visited[a][b]=true;
                    distant[a][b]+=d;
                    dfs(a,b,distant,d,visited);
                }
            }
        }
        return distant;
    }
    
}

• time limit 뜸

  • 논외로, BFS 알고리즘 익히려는 취지로는 잘했다. 맞음.

  class Solution {
      //317문제와는 다르게, 안가는 곳은 없으니까 세명다 닿을 수 있는 거리인지는 생각하지 않아도 된다.어차피 다 갈 수 있다.
      public int minTotalDistance(int[][] grid) {
          int[][] distant = new int[grid.length][grid[0].length];
          for(int i=0;i<grid.length;i++){
              for(int j=0;j<grid[0].length;j++){
                  if(grid[i][j]==1){
                      boolean[][] visited = new boolean[grid.length][grid[0].length];
                      visited[i][j]=true;
                      distant = dfs(i,j,distant,0,visited);
                  }
              }
          }
          int min= Integer.MAX_VALUE;
          // 아 이렇게하면, 흠.. sort 시간도 신경써줘야하는구나.. => BFS 접근, time limit뜬다.
          for(int i=0;i<grid.length;i++){
              for(int j=0;j<grid[0].length;j++){
                  min= Math.min(distant[i][j],min);
              }}
          return min;
      }
        
      public int[][] dfs(int i, int j , int[][] distant, int d, boolean[][] visited){
          int[][] position ={{1,0},{-1,0},{0,-1},{0,1}};
          Queue<int[]> q = new LinkedList<>();
          q.add(new int[]{i,j});
          while(!q.isEmpty()){
              int size= q.size();
              d++;
              for( int z =0;z<size;z++){
                  int[] index=q.poll();
                  for (int[] ind : position){
                      int a= ind[0]+index[0];
                      int b= ind[1]+index[1];
                      if(!(a<0 || a>= distant.length || b<0 || b>=distant[0].length)){
                          if(!visited[a][b]){
                              visited[a][b]=true;
                              distant[a][b]+=d;
                              q.add(new int[] {a,b});
                  }
              }        
          }
              }
          }
    
    
          return distant;
      }
        
  }