[백준/boj] 14502: 연구소 (Java) / BFS / 조합 / 브루트포스

10개월 전의 내가 35번 틀리고 포기했던 문제 풀었다 ☻ 

문제

14502번: 연구소

풀이

import java.util.*;
import java.io.*;

public class Main_BOJ_14502_연구소 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int[][] map, mapClone;
	static int N, M, maxNum= 0;
	static int[] combList = new int[3];
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};
	static ArrayList<Pos> safe = new ArrayList<Pos>();
	static Deque<Pos> virus = new ArrayDeque<Pos>();
	static int safeCnt = 0;
	static boolean flag = false;
	private static class Pos{
		int x;
		int y;
		
		public Pos(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	
	public static void main(String[] args) throws Exception {
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		map = new int[N][M];
		mapClone = new int[N][M];
		int value;
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<M; j++) {
				value = Integer.parseInt(st.nextToken());
				map[i][j] = value;
				mapClone[i][j] = value;
				if(map[i][j] == 0) {
					safe.add(new Pos(i, j));
				}
			}
		}
		combination(0, 0);
		System.out.println(maxNum);
		
	}

	private static void combination(int cnt, int start) {
		if(cnt == 3) {
			mapCopy();
			for(int i: combList) {
				map[safe.get(i).x][safe.get(i).y]= 1; 
			}
			spreadVirus();
			maxNum = Math.max(maxNum, cntZero());
			return;
		}

		for(int i= start; i< safe.size(); i++) {
			combList[cnt] = i;
			combination(cnt+1, i+1);
		}
	}

	private static void mapCopy() {
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				map[i][j] = mapClone[i][j];
				if(map[i][j] == 2) {
					virus.add(new Pos(i, j));
				}
			}
		}
	}
	
	private static void spreadVirus() {
		int nx, ny;
		Pos pos;
		while(!virus.isEmpty()) {
			pos = virus.poll();
			for(int i=0; i<4; i++) {
				nx = pos.x + dx[i];
				ny = pos.y + dy[i];
				if(!isRange(nx, ny) || map[nx][ny] > 0) continue;
				map[nx][ny] = 2;
				virus.add(new Pos(nx, ny));
			}
		}
	}
	
	private static boolean isRange(int x, int y) {
		return x < 0 || x >= N || y < 0 || y >= M ? false : true;
	}
	
	private static int cntZero() {
		int cnt =0;
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(map[i][j] == 0)
					cnt++;
			}
		}
		return cnt;
	}
}

1. map[i][j] == 0 일 때, safe ArrayList 에 담는다. 

2. combination

• 3개의 벽 조합 생성 : combList 에는 int 값이 3개 담기는데 이는 safe ArrayList의 인덱스이다. 
• cnt == 3 즉, combList에 3개가 담기면 1. 맵 초기화 2. 벽 세우기 3. 바이러스 퍼뜨리기 4. 0의 개수 세기 5. max값 갱신 다섯 단계를 진행한다. 
• 모든 조합에 따른 안전 영역 숫자를 세서 max값을 갱신했으면
• maxNum 출력