삼성 SW 역량 테스트 기출 문제 : 연구소

https://www.acmicpc.net/problem/14502

14502번: 연구소

 

// 코드

import java.util.*;
import java.io.*;
 
class Main{ 
  
  static int N, M, result;
  static int[][] map;
  static final int[][] DIR = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
  static int[][] mapCpy;
  static boolean[][] visited;
  
  // 가스 확산
  static void bfs() {
    
    Deque<Integer> deq = new ArrayDeque<>();
    mapCpy  = new int[N][M];
    visited = new boolean[N][M];
    
    // 원본을 보존하기 위해서 복사하면서 
    // 바이러스의 위치 값을 미리 넣어둔다.
    for(int row=0; row<N; ++row) {
      for(int col=0; col<M; ++col) {
        mapCpy[row][col] = map[row][col];
        // row * 10 + col : 하나의 정수 값으로 모든 int 값을 복원할 수 있다.
        if(mapCpy[row][col] == 2) { 
          deq.add(row * 10 + col);
          visited[row][col] = true;
        }
      }
    }
    
    // 본격적인 bfs시작
    while(!deq.isEmpty()) {
      int cur = deq.pop();
      
      int curRow = cur / 10;
      int curCol = cur % 10;
      
      for(int i=0; i<4; ++i) {
        int ny = curRow + DIR[i][0];
        int nx = curCol + DIR[i][1];
        
        if(ny < 0 || ny >= N || nx < 0 || nx >= M) continue;
        if(visited[ny][nx] || mapCpy[ny][nx] != 0) continue;
        
        mapCpy[ny][nx]  = 2;
        visited[ny][nx] = true;
        deq.push(ny * 10 + nx); 
      } 
    }
    
    // 0의 최댓값을 찾는다.
    int candi = 0;
    for(int i=0; i<N; ++i) for(int j=0; j<M; ++j) if(mapCpy[i][j] == 0) ++candi;
    result = Math.max(candi, result);
  }
  
  // 벽을 세운다.  
  static void pickDfs(int cnt, int startRow, int startCol) {
    // 다리 3개를 다했을 때
    if(cnt >= 3) {
      bfs();
      return; 
    }
    
    for(int row = startRow; row < N; ++row) {
      for(int col = startCol; col < M; ++col) {
        // 빈공간인 경우만 벽을 세울 수 있다.
        if(map[row][col] == 0) {
          map[row][col] = 1;
          pickDfs(cnt + 1, row, col);
          map[row][col] = 0;
        }
      }
      startCol = 0;
    }
    
  }
  
  // main
  public static void main(String[] args) throws Exception{
    // Please Enter Your Code Here
    BufferedWriter bw  = new BufferedWriter(new OutputStreamWriter(System.out));
    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][];
    for(int i=0; i<N; ++i) map[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    
    pickDfs(0, 0, 0);
    
    bw.write(String.valueOf(result));
    bw.flush();
    bw.close();
    br.close();
  } 
}