[JAVA][BOJ] 14502. 연구소

첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8)

둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다. 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다.

빈 칸의 개수는 3개 이상이다.

라는 문구가 가장 먼저 눈에 띄었고

N이 8이하 벽은 3개 라는 것에 착안점을 두어 

3중 for문으로 벽을 세울 인덱스를 정한뒤 바이러스가 퍼지도록 bfs를 하여 그 때 남은 0의 갯수를 세어 확인하였다.

3중 for문을 작성할때 ( 3개의 점을 고를때 ) 같은 점을 찍지 않도록 그리고 0인점만 골라 벽을 세울 수 있도록 다음과 같이 작성하였다.

첫번째 for문 기준으로 idx / M(가로크기) 는 일반적인 배열의 i 즉, row가 되고  idx % M 은 일반적인 배열의 j 즉, col이 된다.

for(int idx1 = 0; idx1<N*M-2; idx1++) {
    if( map[idx1/M][idx1%M] != 0) continue;
    for(int idx2 = idx1+1; idx2< N*M-1; idx2++) {
        if( map[idx2/M][idx2%M] != 0) continue;
        for(int idx3 = idx2+1; idx3< N*M; idx3++) {
            if( map[idx3/M][idx3%M] != 0) continue;
                simul( idx1/M, idx1%M, idx2/M, idx2%M, idx3/M, idx3%M );
            }
        }
    }
}

전체 코드는 다음과 같다.

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
public class Main14502 {
    static Queue<Node> qu;
    static int N;
    static int M;
    static int[][] map;
    static int[] x = {0, 0, 1, -1};
    static int[] y = {1, -1, 0, 0};
    static int result;
    static int[][] temp;
    
    static class Node{
        int i, j;
        Node(int i, int j){
            this.i = i;
            this.j = j;
        }
    }
    
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] s = br.readLine().split(" ");
        N = Integer.parseInt(s[0]);
        M = Integer.parseInt(s[1]);
        map = new int[N][M];
        qu = new LinkedList<>();
        result = 0;
        temp = new int[N][M];
        for(int i=0; i<N; i++) {
            s = br.readLine().split(" ");
            for(int j=0; j<M; j++) {
                map[i][j] = Integer.parseInt(s[j]);
            }
        }
        
        for(int idx1 = 0; idx1<N*M-2; idx1++) {
            if( map[idx1/M][idx1%M] != 0) continue;
            
            for(int idx2 = idx1+1; idx2< N*M-1; idx2++) {
                if( map[idx2/M][idx2%M] != 0) continue;
                
                for(int idx3 = idx2+1; idx3< N*M; idx3++) {
                    if( map[idx3/M][idx3%M] != 0) continue;
                    
                    simul( idx1/M, idx1%M, idx2/M, idx2%M, idx3/M, idx3%M );
                }
            }
        }
        
    
        bw.write(""+result+"\n");
        br.close();
        bw.close();
    }
    
    static void simul(int i, int j, int q, int w, int e, int r) {
        for(int y=0; y<N; y++) {
            for(int x=0; x<M; x++) {
                temp[y][x] = map[y][x];
                if(temp[y][x]==2) qu.offer(new Node(y,x));
            }
        }
        temp[i][j] = 1;
        temp[q][w] = 1;
        temp[e][r] = 1;
        Node node = null;
        int ni = 0;
        int nj = 0;
        while(!qu.isEmpty()) {
            node = qu.poll();
            temp[node.i][node.j] = 2;
            for(int z=0; z<4; z++) {
                ni = node.i + x[z];
                nj = node.j + y[z];
                if( ni < 0 || nj < 0 || ni > N-1 || nj > M-1 ) continue;
                if( temp[ni][nj] == 1 || temp[ni][nj] == 2) continue;
                qu.offer(new Node(ni, nj));
                
            }
        }
        int cnt = 0;
        for(int y=0; y<N; y++) {
            for(int x=0; x<M; x++) {
                if(temp[y][x] == 0) cnt++;
            }
        }
        if( result < cnt ) result = cnt;
 
    }
 
}