음료수 얼려먹기 java 이취코테 149p

dfs ,bfs 둘다 구현
완탐으로 그래프 순회하며 boolean리턴 하는 함수로 작성하여 효율성 높임

import java.io.*;
import java.util.Queue;
import java.util.LinkedList;

class Main {
  static char[][] graph;
  static int[] dx={1,-1,0,0}, dy={0,0,1,-1};
  static int R,C;
  
  public static void main(String[] args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String[] sizeOfMap = br.readLine().split(" ");
    R = Integer.parseInt(sizeOfMap[0]); C = Integer.parseInt(sizeOfMap[1]);
    graph = new char[R][]; // 행의 사이즈만 선언하여 char array바로 할당할 수 있도록
    for (int i=0; i< R;i++){
      graph[i] = br.readLine().toCharArray();
    }
    int res=0;
    for(int r=0; r<R; r++){
      for (int c=0; c<C; c++){
        //if(dfs(r,c)) res++;
        if(bfs(r,c)) res++;
        /**
        boolean 리턴 하도록 하여 바로바로 처리(visit 배열 추가로 소모할 필요없다.)
        */
      }
    }
    System.out.println(res);
  }
  public static boolean dfs(int x, int y){
    if (graph[x][y] == '1') return false;
    graph[x][y] = '1';
    for (int i=0; i<4; i++){
      int nx = x+dx[i], ny = y+dy[i];
      if(nx<0||nx>R-1 || ny<0 || ny>C-1) continue;
      dfs(nx,ny);
    }
    return true;
    
  }
  
  public static boolean bfs(int x, int y){
    if (graph[x][y] == '1') return false;
    
    Queue<int[]> q = new LinkedList<>();
    graph[x][y] = '1';
    q.offer(new int[] {x,y});
    
    while(!q.isEmpty()){
      int[] cord = q.poll();
      int r=cord[0], c=cord[1];
      for (int i=0; i<4; i++){
        int nx = r+dx[i], ny = c+dy[i];
        if(nx<0||nx>R-1 || ny<0 || ny>C-1) continue;     
        if(graph[nx][ny] == '0'){
          graph[nx][ny] = '1';
          q.offer(new int[] {nx,ny});
        }
        
      }
    }
    return true;
  }
  
}