[백준온라인] 14502번 연구소

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

14502번: 연구소

문제 요약 : 벽을 3개 세워 만들 수 있는 안전한 공간의 최대 크기

입력	출력
3 ≤ N,M(크기) ≤ 8 [N][M] = 0(빈 칸), 1(벽), 2(가스)	벽을 3개 세운 후 안전한 공간의 최대 크기

 

JAVA

채점 번호	아이디	문제 번호	결과	메모리	시간	언어	코드 길이
16355178	cbkpar	14502	맞았습니다!!	15980KB	160ms	Java	1596B

import java.io.*;

public class Main {
	static int n,m;
	static int[][] map;
	static int[][] test;
	static int[][] gas_loc = new int[10][2];
	static int ngas=0;
	static int safe=0;

	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int i,j;
		String str = "";
		str = br.readLine();
		String[] arr = str.split(" ");
		n = Integer.parseInt(arr[0]);
		m = Integer.parseInt(arr[1]);
		map = new int[n][m];
		test = new int[n][m];
		for(i=0;i<n;i++) {
			str = br.readLine();
			arr = str.split(" ");
			for(j=0;j<m;j++) {
				map[i][j] = Integer.parseInt(arr[j]);
				if(map[i][j]==2) {//가스라면 위치저장
					gas_loc[ngas][0]=i;
					gas_loc[ngas][1]=j;
					ngas++;
				}
			}
		}
		wall(0,0);
		System.out.println(safe);
	}
	static void wall(int w, int k) {
		if(k==3) {//벽이 3개라면
			for(int i=0;i<n;i++) {
				System.arraycopy(map[i], 0, test[i], 0, m); // 배열복사
			}
			for(int i=0;i<ngas;i++) {
				gas(gas_loc[i][0],gas_loc[i][1]); // 저장된 가스 위치에서 가스 확산
			}
			int safecnt = 0;
            //안전구역 개수 계산
			for(int i=0;i<n;i++) {
				for(int j=0;j<m;j++) {
					if(test[i][j]==0) safecnt++;
				}
			}
			safe = Math.max(safe, safecnt);
			return;
		}
		for(int i=w;i<n*m;i++) {//왼쪽에서 오른쪽, 위에서 아래 순으로 벽을 세움
			if(map[i/m][i%m]==0) {//벽을 세울 수 있다면
				map[i/m][i%m]=1;
				wall(i+1,k+1);
				map[i/m][i%m]=0;
			}
		}
	}
	static void gas(int y, int x) {
    //가스 확산
		if(y>0&&test[y-1][x]==0) {//상
			test[y-1][x]=2;
			gas(y-1,x);
		}
		if(y<n-1&&test[y+1][x]==0) {//하
			test[y+1][x]=2;
			gas(y+1,x);
		}
		if(x>0&&test[y][x-1]==0) {//좌
			test[y][x-1]=2;
			gas(y,x-1);
		}
		if(x<m-1&&test[y][x+1]==0) {//우
			test[y][x+1]=2;
			gas(y,x+1);
		}
	}
}