[백준] 2234 성곽

문제보기

BFS 연습~!

import java.util.*;
import java.io.*;
// 좌표 담을 클래스
class Pair{
  int x;
  int y;
  Pair(int x, int y){
    this.x = x;
    this.y = y;
  }
}
public class Main{
  static int n;
  static int m;
  static String[][] map;
  static int[][] d;
  static int max;
  static int[] dx = {1, 0, -1, 0}; // 차례대로 남동북서 표시 
  static int[] dy = {0, 1, 0, -1};
  static int[] room;

  static void bfs(int a, int b, int cnt){
    Queue<Pair> q = new LinkedList<>();
    q.add(new Pair(a, b));
    d[a][b] = cnt;
    int area = 1;

    while(!q.isEmpty()){
      Pair p = q.remove();
      int x = p.x;
      int y = p.y;
      String s = map[x][y];

      for(int k = 0 ; k < 4 ; k++ ){
        int nx = x + dx[k];
        int ny = y + dy[k];
				// 방문 조건 : 벽이 없고 & 맵 내에 있으며 & 방문한 적 없어야 함 
        if(map[x][y].charAt(k) == '0' && nx >= 0 && ny >= 0 && nx < n && ny < m && d[nx][ny] == 0){
          d[nx][ny] = cnt;
          area++;
          q.add(new Pair(nx, ny));
        }
      }

    }
    // 탐색이 끝나면 room에 저장 
    if( area > max ) max = area;
    room[cnt] = area;
  }

  public static void main(String []args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    m = Integer.parseInt(st.nextToken());
    n = Integer.parseInt(st.nextToken());
    map = new String[n][m];
    String[] zero = {"" , "0" , "00", "000"}; // 앞에 0 모자란거 채워줄 용도

    for(int i = 0 ; i < n ; i++){
      st = new StringTokenizer(br.readLine());
      for(int j = 0 ; j < m ; j++ ){
        // 이진수로 변환
        String s = Integer.toBinaryString(Integer.parseInt(st.nextToken()));
        // 네자리 채워서 저장 
        map[i][j] = zero[4-s.length()] + s;

      }
    }

    d = new int[n][m];
    int cnt = 1;
    max = 0;
    room = new int[n*m+1];

    for(int i = 0 ; i < n ;i++){
      for(int j = 0 ; j < m ; j++){
        if(d[i][j] == 0){ // 방문한 적 없다면 bfs
          bfs(i, j, cnt++);
        }
      }
    }
		
    // 3번 풀이를 위한 인접리스트 만들기 
    ArrayList<Integer>[] list = (ArrayList<Integer>[]) new ArrayList[cnt];
    for(int i = 0 ; i < cnt ; i++ ){
      list[i] = new ArrayList<Integer>();
    }
    for(int i = 0 ; i < n-1 ; i++){
      for(int j = 0 ; j < m-1 ; j++){
        // 우측, 아래측 검사
        int u = d[i][j];
        int v = d[i][j+1];
        int w = d[i+1][j];

        if( u != v ){
          list[u].add(v);
        }
        if( u != w ){
          list[u].add(w);
        }
      }
      // 예외처리 : m-1 일때는 아랫쪽만 검사 
      int u = d[i][m-1];
      int v = d[i+1][m-1];
      if( u != v ) list[u].add(v);
    }
    // 예외처리 : n-1일 때는 오른쪽만 검사 
    for(int j = 0 ; j < m-1 ; j++ ){
      int u = d[n-1][j];
      int v = d[n-1][j+1];
      if( u != v ) list[u].add(v);
    }

		// 합쳐보기 
    int union = 0;
    for(int i = 0 ; i < cnt ; i++ ){
      for(int j = 0 ; j < list[i].size() ; j++){
        int sum = room[i] + room[list[i].get(j)]; 
        if( union < sum ) union = sum;
      }
    }

    System.out.println(cnt-1);
    System.out.println(max);
    System.out.println(union);

  }
}