[백준] 14502 연구소

문제보기

삼성 역태 준비중!

뭔가 벽을 쌓는 기준이 있을것만 같았는데 (1 기준 대각선으로 쌓기?) 뭔가 예외도 많을것 같고.. n,m값도 상당히 작아서

브루트 포스로 빠르게 풀었다. for문 지옥이 되어버림

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[] dx = {1, -1, 0, 0};
  static int[] dy = {0, 0, 1, -1};
  static int[][] map;
  static int[][] newMap;
  static int n;
  static int m;
  
  // 바이러스 확산을 위한 bfs
  static void bfs(int i, int j){
    Queue<Pair> q = new LinkedList<>();
    q.add(new Pair(i, j));

    while(!q.isEmpty()){
      Pair p = q.remove();
      int x = p.x;
      int y = p.y;

      for(int k = 0 ; k < 4 ; k++ ){
        int nx = x + dx[k];
        int ny = y + dy[k];

        if(nx >= 0 && ny >= 0 && nx < n && ny < m){
          if(newMap[nx][ny] == 0){
            q.add(new Pair(nx,ny));
            newMap[nx][ny] = 2;
          }
        }
      }
    }
  }


  public static void main(String []args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    n = Integer.parseInt(st.nextToken());
    m = Integer.parseInt(st.nextToken());
    map = new int[n][m];
    int[][] virus = new int[10][2]; // 바이러스 위치를 담을 배열
    int vidx = 0; // 바이러스의 갯수를 저장 

    for(int i = 0 ; i < n ; i++ ){
      st =  new StringTokenizer(br.readLine());
      for(int j = 0 ; j < m ; j++ ){
        map[i][j] = Integer.parseInt(st.nextToken());
        if(map[i][j] == 2){
          virus[vidx][0] = i;
          virus[vidx++][1] = j;
        }
      }
    }

    int max = 0;
		
    // for문 지옥에 온것을 환영한다!
    // i1, j1 은 첫번째 세울 벽의 좌표, i2~j3도 같은 의미 
    for(int i1 = 0 ; i1 < n ; i1++ ){
      for(int j1 = 0 ; j1 < m ; j1++){
        if(map[i1][j1] != 0) continue;
        for(int i2 = i1 ; i2 < n ; i2++ ){
          for(int j2 = 0 ; j2 < m ; j2++ ){
            if( (i2 == i1 && j2 <= j1) || map[i2][j2] != 0) continue;
            for(int i3 = i2 ; i3 < n ; i3++){
              for(int j3 = 0 ; j3 < m ; j3++){
                if((i3 == i2 && j3 <= j2) || map[i3][j3] != 0) continue;
								// 벽을 세워준다 (1로 해도 상관없다. 나는 중간출력시 구분하고자 3으로 준것 뿐)
                map[i1][j1] = map[i2][j2] = map[i3][j3] = 3;
                
                // 바이러스 확산 처리 된 맵을 새로 만들어주자 
                newMap = new int[n][m];
                for(int i = 0 ; i < n ; i++){
                  System.arraycopy(map[i], 0, newMap[i], 0, m);
                }
                for(int k = 0 ; k < vidx ; k++){
                  bfs(virus[k][0], virus[k][1]); // 존재하는 모든 바이러스에 대해 bfs
                }

                int area = 0; // safe zone
                for(int i = 0 ; i < n ; i++){
                  for(int j = 0 ; j < m ; j++){
                    if(newMap[i][j] == 0){
                      area++;
                    }
                  }
                }

                if(area > max){
                  max = area;
                }
                map[i1][j1] = map[i2][j2] = map[i3][j3] = 0; // 초기화
              }
            }
          }
        }
      }
    }

    System.out.println(max);

  }
}