[BOJ] 14502. 연구소 G5 JAVA

---

---

문제 이해

- 배열의 값 0 (빈칸), 1 (벽), 2 (바이러스)으로 나누어진다. - 바이러스는 4방 ( 상/하/좌/우 )으로 이동한다. - 벽은 3개가 있으며, 3개 모두다 세워야한다. - 안전영역은 벽으로 둘러쌓여있는 안쪽 영역이다 - 안전영역의 최대 값을 구하자.

아이디어

일단 코드 흐름을 잡아보았다. 1. 벽 3개를 랜덤하게 세우고,,,(그 위치는 빈칸이어야한다) 2. 바이러스를 퍼뜨리고 3. 안전지대 영역을 세고 4. Max값을 갱신해주고. 이거를 벽을 세우는 경우의 수 만큼 반복하면 될 것 같았다. 프로세스야 그렇다 쳐도.. 1번에서 고민이 좀많았는데 결국은 nCr로 풀어야겠다고 생각을 해냈고, 조합으로 랜덤한 3개의 인덱스를 뽑아낸다.( r은 어차피 벽이 3개로 고정되어있다. ) 근데 또!!!문제가 생겼다ㅜ 인덱스 3개를 뽑아냈을 때 얘를 어떻게 행,열로 변환을 할거냐였다. 고민을 또 하다가 N*M = 2*2 배열을 그려서 고민해봤는데 이렇게 N*M배열이 있을 때 배열의 인덱스는 그림과 같다. 그럼이제 인덱스를 3개 뽑아야하는데, 범위를 어디까지 잡아서 뽑을지가 문제였다. 그래서 0부터 3까지가 되려면 for(int i=0;i<N*M;++i)로 답을 해결할 수 있었다. 자 이제 행,열을 어떻게 나눌지가 문제였는데 행은 신경안써도 되고 열만 신경쓰면 된다. 자 그럼 예를들어서 1,2,3을 뽑았다고 가정하면, 우리는 행과 열을 구해야한다. 2를 가지고 구해보자. 행은 그냥 뽑은 인덱스에서 열크기만큼 나눈 몫을 구하면 구해진다. (왜냐면 M=2인데 열보다 커져버리면 다음행으로 넘어가져야하니까) 그러면 2/M=1이니까 1행에 들어가면 된다. 그럼 열은??? 어차피 열은 0이거나 1이거나 이다. 즉 열길이만큼 나눈 나머지!가 된다. 2%M = 0 그럼 인덱스 2번이 뽑혔을 때 실제 배열에서는 arr[2/M][2%M]의 위치를 뽑았다는 거다!!!! 이거 해결하고 나서는 그냥 쭉 풀 수있었다... 나중에 까먹을까봐 정리해둠

코드가 조금 지저분한데,, 급하게 올린다고 ㅎㅎ; 나중에 다시 정리해서 올려야겠댜

코드

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

public class Main {

	static int Int(String s) {
		return Integer.parseInt(s);
	}

	static int[][] arr, copy;
	static int N, M, R = 3, max = Integer.MIN_VALUE;
	static int[] input = new int[R];			// 뽑힌 인덱스가 담길 배열 (3개만담김)
	static final int empty = 0, wall = 1, virus = 2;
	static ArrayList<Pos> viruses = new ArrayList<>();
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Int(st.nextToken()); 				// 행
		M = Int(st.nextToken()); 				// 열
		arr = new int[N][M]; 					// 원본 배열
		copy = new int[N][M]; 					// 벽을 계속 놓아보기 위한 배열
		for (int i = 0; i < N; ++i) {// 입력을받는다.
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < M; ++j) {
				arr[i][j] = Int(st.nextToken());
				if(arr[i][j] == virus) viruses.add(new Pos(i,j));
			}
		}
		Combination(0, 0, 0);
		System.out.println(max);
	}

	static void copyOrigin() { // 깊은 복사해야함
		for (int i = 0; i < copy.length; ++i)
			System.arraycopy(arr[i], 0, copy[i], 0, arr[0].length);
	}
	
	static class Pos{
		int x, y;
		public Pos(int x, int y) {
			this.x =x;
			this.y=y;
		}
	}
	
	static int[] dx = {-1,1,0,0};
	static int[] dy = {0,0,-1,1};
	
	static void bfs() {
		Queue<Pos> q = new LinkedList<>();
		for(Pos p : viruses) q.offer(p);
		boolean[][] isVisited = new boolean[N][M];
		isVisited[q.peek().x][q.peek().y] = true;
		
		while(!q.isEmpty()) {
			Pos current = q.poll();
			copy[current.x][current.y]= virus; 
			for(int d=0;d<4;++d) {
				int nx= current.x  + dx[d];
				int ny = current.y + dy[d];
				if(0<=nx&&nx<N && 0<=ny &&ny<M&& 
				!isVisited[nx][ny] &&copy[nx][ny]==empty) {
					isVisited[nx][ny] = true;
					q.offer(new Pos(nx,ny));
				}
			}
		}
	}
	
	static int getCount() {
		int cnt =0;
		for(int i=0;i<N;++i) {
			for(int j=0;j<M;++j) {
				if(copy[i][j] == empty) cnt++;
			}
		}
		return cnt;
	}
	
	static void Combination(int start, int idx, int cnt) {
		if (cnt == R) {
			copyOrigin();// 배열을 복사하고                 열기준으로만 생각하면 됌.
			for (int x = 0; x < R; ++x) copy[input[x] / M][input[x] % M] = 1; // 실제로 벽을 세워본다.
			bfs();// bfs로 바이러스를 퍼뜨려본다.
			max = Math.max(max, getCount());// 안전영역을 카운트 한다.
			return;
		}

		for (int i = start; i < N * M; ++i) {
			if (arr[i / M][i % M] == empty) {	// 빈공간에만 벽을 세울수 있음.
				input[idx] = i;
				Combination(i + 1, idx + 1, cnt + 1);
			}
		}
	}
}

 

 

 

---

집사는개발자가되고파