[BAEKJOON_14502 - JAVA] 연구소

문제

 

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

14502번: 연구소

 

 

과정

1. 벽을 3개 세운다.
2. 벽을 세운 상태로 바이러스를 확산 시킨다
3. 안전 영역을 구한다. 
4. 위의 과정을 반복하며 안전영역의 최댓값을 갱신한다.

 

 

풀이

• 위와 같은 과정을 먼저 설계한뒤 시작.
• 입력을 받으면서 바이러스의 좌표를 arrayList에 삽입.
• 벽을 세우는 method는 모든 벽을 세우는 조합을 찾기에 DFS를 활용.
• virus의 확산은 BFS를 활용.
• virus의 확산이 끝난경우, 안전영역을 구한 후 최대값 갱신.

 

 

문제 해결

결과값이 지속적을 0이 출력되어 확인을 해봤더니
기존 1차원 배열의 경우 clone()으로 깊은 복사를 했지만, 2차원 배열의 경우 주소값을 참조함.
이중 for문을 통한 깊은 복사로 문제 해결.

→ 2차원 배열의 경우 clone() 메소드를 통한 깊은 복사가 되지 않는다. 

 

 

알고리즘 지식

• 브루트 포스 (BFS, DFS)

 

 

JAVA 코드

 

/*
 * 1. 벽을 3개씩 맵에 세운다.
 * 
 * 2. 벽을 세운 상태로 바이러스를 전염.
 * 
 * 3. 값을 구한 후 최대값 비교.
 * 
 * 2차원 배열은 clone을 활용한 deep clone이 불가능.
 */

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class virusPoint {
	int row;
	int col;

	public virusPoint(int row, int col) {
		super();
		this.row = row;
		this.col = col;
	}

}

public class BJ14502_연구소_김민건 {

	static int N, M, max; // 가로 세로 최대값
	static int[][] map; // 입력받는 맵
	static int[][] wall; // 벽을 놓을 맵
	static int[] dy = { -1, 1, 0, 0 }; // 상 하 좌 우
	static int[] dx = { 0, 0, -1, 1 };
	static ArrayList<virusPoint> virusList;

	// 범위 검사
	public static boolean isValid(int row, int col) {
		if (row < 0 || row >= N || col < 0 || col >= M)
			return false;
		return true;
	}

	// map 깊은 복사
	public static int[][] copy(int [][] arr) {

		int[][] copy = new int[N][M];

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				copy[i][j] = arr[i][j];
			}
		}
		return copy;
	}

	// 벽을 세우는 경우
	public static void makeWall(int depth) {

		if (depth == 3) {
			spreadVirus();
			return;
		}

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (wall[i][j] == 0) { // 빈칸인 경우
					wall[i][j] = 1; // 벽 건설
					makeWall(depth + 1);
					wall[i][j] = 0; // 다음 경우의 수를 위해 복구
				}
			}
		}
	}

	// 벽을 세웠을 경우, virus 전염
	private static void spreadVirus() {

		int[][] copyWall = copy(wall); // 바이러스를 확장 시킬 복사 맵

		// virus를 담는 과정
		Queue<virusPoint> vq = new LinkedList<virusPoint>(); // virus를 담는 큐
		for (int i = 0; i < virusList.size(); i++) {
			vq.offer(new virusPoint(virusList.get(i).row, virusList.get(i).col));
		}

		// virus 전염 시작
		while (!vq.isEmpty()) {
			int row = vq.peek().row;
			int col = vq.poll().col;

			for (int k = 0; k < 4; k++) {
				int nextRow = row + dy[k];
				int nextCol = col + dx[k];

				// 범위 && 빈칸인 경우
				if (isValid(nextRow, nextCol) && copyWall[nextRow][nextCol] == 0) {
					copyWall[nextRow][nextCol] = 2;
					vq.offer(new virusPoint(nextRow, nextCol));
				}

			}
		} // end of spread

		// 안전구역 크기 체크 후 비교
		int sc = countSafe(copyWall);
		max = Math.max(max, sc);
	}

	// 안전구역 크기
	public static int countSafe(int[][] copyWall) {
		int sc = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (copyWall[i][j] == 0) {
					sc++;
				}
			}
		}
		return sc;
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;

		st = new StringTokenizer(br.readLine());
		virusList = new ArrayList<virusPoint>();
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		map = new int[N][M];
		max = 0;

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				// 입력을 받으면서 바이러스 초기값 탐색
				if (map[i][j] == 2) {
					virusList.add(new virusPoint(i, j));
				}
			}
		} // end of input

		// 3개의 벽을 세우기 위한 copy map
		wall = copy(map);

		// 벽 세우기 시작
		makeWall(0);

		System.out.println(max);
	} // end of main

}