반응형
문제
https://www.acmicpc.net/problem/14502
14502번: 연구소
인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다.
www.acmicpc.net
과정
- 벽을 3개 세운다.
- 벽을 세운 상태로 바이러스를 확산 시킨다
- 안전 영역을 구한다.
- 위의 과정을 반복하며 안전영역의 최댓값을 갱신한다.
풀이
- 위와 같은 과정을 먼저 설계한뒤 시작.
- 입력을 받으면서 바이러스의 좌표를 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
}
반응형
'Algorithm > 문제 풀이' 카테고리의 다른 글
[BAEKJOON_2636 - JAVA] 치즈 (0) | 2020.05.16 |
---|---|
[BAEKJOON_14500 - JAVA] 테트로미노 (0) | 2020.05.11 |
[BAEKJOON_4485 - JAVA] 녹색 옷 입은 애가 젤다지? (2) | 2020.05.03 |
[BAEKJOON_15686 - JAVA] 치킨배달 (0) | 2020.05.02 |
[SWEA_4366 - JAVA] 정식이의 은행업무 (0) | 2020.05.01 |