[BOJ] - 연구소 / 14502번 (Java)

[BOJ] - 연구소 / 14502번 (Java)

[BOJ] - 연구소 / 14502번 (Java)

1. 문제 접근

N x N 크기의 연구소에 2이상 10이하 개수를 갖는 바이러스가 있을 때, 총 3개의 벽을 빈 공간에 세워 얻을 수 있는 안전영역의 최대 크기를 구하면 된다.

 

먼저 입력(N)의 크기가 최대 8로 크지 않다. 

 

완전 탐색을 통해 나이브하게 경우의 수를 살펴 보면 64 Combination 3 (벽을 선택하는 경우의 수) x 바이러스를 퍼트리는 시간(<64) 이므로 300만을 넘지 않는다.

 

따라서 완전 탐색으로 구현하였다.

 

먼저 빈 공간의 위치 정보를 `Pos`형 일차원 배열에 저장했다.

if (map[row][col] == 0) {
    // 빈 공간 위치 정보 저장
    elementList[elementCnt++] = new Pos(row, col);
}

 

그 후 Combination을 통해 `elementList[]`에서 3개의 위치를 선정했다.

 

따라서 재귀로 구현한 조합의 기저조건은 `selectIdx == 3`이 될 때가 된다.

 

해당 조합에 대해 1. 벽을 세우고, 2.바이러스를 퍼트리고, 3. 다시 벽을 허무는 과정을 거치게 된다.

 

바이러스를 퍼트렸다면 안전영역의 개수를 구해야한다.

 

벽은 빈 공간에 세우므로 기존의 안전 영역의 크기에서 3을 빼야한다.

 

또한 기존의 안전영역을 바이러스가 침범하되, 원래 초기 위치의 바이러스 위치는 기존의 안전영역으로 카운팅 되지 않았으므로 추가적으로 뺀 영역의 크기만큼 더해준다.

if (selectIdx == WALL_NUMBER) {
    // 선정한 위치 벽 세우기
    for (Pos wallPos : selectList)
        map[wallPos.x][wallPos.y] = 1;

    int virusArea = countVirusArea();

    // 선정한 위치 벽 허물기
    for (Pos wallPos : selectList)
        map[wallPos.x][wallPos.y] = 0;

    // 안전 영역크기 계산 후 갱신
    // 빈공간 - 벽의 개수(3) - 바이러스 영역 + 기존에 바이러스가 존재하는 영역의 수
    ans = Math.max(ans, emtpySpace - 3 - virusArea + virusSpace);
    return;
}

 

이후 기존의 안전영역의 크기와 비교하여 갱신하게 된다.

 

---

2. 코드

package boj;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

/**
 * [BOJ] - 연구소 / 14502번 
 * @author JinHxxxxKim
 * 
 * 1. 행, 열에 대해 3개를 선택하는 조합으로 완전 탐색 진행
 * 2. 해당 좌표가 이미 벽, 바이러스라면 PASS
 * 		2-1. 기저조건(3개 모두 선택했다면): 바이러스에 대해 BFS 실행 후, 남아있는 영역 계산
 * 		2-2. 안전 지대 영역의 수 갱신
 */
public class Sol_14502 {
	private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	private static StringTokenizer st;

	static final int[] dx = new int[] { -1, 0, 1, 0 };
	static final int[] dy = new int[] { 0, 1, 0, -1 };
	static final int WALL_NUMBER = 3;

	static int rowMax, colMax;
	static int[][] map;
	static int emtpySpace, virusSpace;
	static int ans;
	static Pos[] initVirusPos;

	// 조합 관련 변수
	static Pos[] selectList;
	static Pos[] elementList;

	public static void main(String[] args) throws Exception {
		st = new StringTokenizer(br.readLine().trim());
		rowMax = Integer.parseInt(st.nextToken());
		colMax = Integer.parseInt(st.nextToken());
		map = new int[rowMax][colMax];
		selectList = new Pos[WALL_NUMBER];

		// 맵 정보 입력
		for (int row = 0; row < rowMax; ++row) {
			st = new StringTokenizer(br.readLine().trim());
			for (int col = 0; col < colMax; ++col) {
				map[row][col] = Integer.parseInt(st.nextToken());
				if (map[row][col] == 0) {
					// 빈 공간 개수 확인
					emtpySpace++;
				} else if (map[row][col] == 2) {
					// 바이러스 개수 확인
					virusSpace++;
				}
			}
		}

		int elementCnt = 0;
		int virusCnt = 0;
		elementList = new Pos[emtpySpace];
		initVirusPos = new Pos[virusSpace];
		for (int row = 0; row < rowMax; ++row) {
			for (int col = 0; col < colMax; ++col) {
				if (map[row][col] == 0) {
					// 빈 공간 위치 정보 저장
					elementList[elementCnt++] = new Pos(row, col);
				} else if (map[row][col] == 2) {
					// 바이러스 위치 정보 저장
					initVirusPos[virusCnt++] = new Pos(row, col);
				}
			}
		}
		
		ans = 0;
		selectWall(0, 0);
		System.out.println(ans);

	}

	/**
	 * 벽 세울 위치를 정하는 메소드
	 * @param selectIdx 선택할 인덱스
	 * @param elementIdx 현재 조회하는 요소의 인덱스
	 */
	private static void selectWall(int selectIdx, int elementIdx) {
		// 기저조건
		if (selectIdx == WALL_NUMBER) {
			// 선정한 위치 벽 세우기
			for (Pos wallPos : selectList)
				map[wallPos.x][wallPos.y] = 1;

			int virusArea = countVirusArea();
			
			// 선정한 위치 벽 허물기
			for (Pos wallPos : selectList)
				map[wallPos.x][wallPos.y] = 0;

			// 안전 영역크기 계산 후 갱신
			// 빈공간 - 벽의 개수(3) - 바이러스 영역 + 기존에 바이러스가 존재하는 영역의 수
			ans = Math.max(ans, emtpySpace - 3 - virusArea + virusSpace);
			return;
		}
		if (elementIdx == emtpySpace) {
			return;
		}

		// 해당 좌표 선택O
		selectList[selectIdx] = elementList[elementIdx];
		selectWall(selectIdx + 1, elementIdx + 1);

		// 해당 좌표 선택X
		selectWall(selectIdx, elementIdx + 1);
	}

	/**
	 * 바이러스가 퍼질 수 있는 영역의 수를 구하는 메소드
	 * @return 바이러스가 퍼질 수 있는 영역의 수
	 */
	private static int countVirusArea() {
		int ret = 0;
		Queue<Pos> q = new ArrayDeque<>();
		boolean[][] isVisited = new boolean[rowMax][colMax];
		// 초기 바이러스 위치 정보 삽입
		for (Pos initVirus : initVirusPos) {
			q.offer(initVirus);
			isVisited[initVirus.x][initVirus.y] = true;
		}
		
		while (!q.isEmpty()) {
			Pos currNode = q.poll();
			ret++;
			int currRow = currNode.x;
			int currCol = currNode.y;

			// 4방 탐색
			for (int dir = 0; dir < 4; ++dir) {
				int tempRow = currRow + dx[dir];
				int tempCol = currCol + dy[dir];

				// 범위 검증
				if (tempRow < 0 || tempCol < 0 || tempRow >= rowMax || tempCol >= colMax)
					continue;
				// 방문 검증
				if (isVisited[tempRow][tempCol])
					continue;
				// 벽 검증
				if (map[tempRow][tempCol] == 1)
					continue;
				
				isVisited[tempRow][tempCol] = true;
				q.offer(new Pos(tempRow, tempCol));
			}
		}
		return ret;
	}

	// 위치 클래스
	static class Pos {
		int x, y;

		public Pos(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}
	}
}

---

3. 디버깅

입력값의 크기가 작은 것을 보고 완전탐색에 대한 아이디어를 떠올릴 수 있어 바로 접근할 수 있었던 문제였다.

 

안전영역의 개수를 계산할 때, 기존 바이러스의 초기위치를 추가적으로 빼는 부분을 조심하여 구현하였다.

---

4. 결과