이번 문제는 솔직히 조금 어려웠다.
일단 벽을 언제 어떻게 설치해야되는지 감이 잡히질 않아 답을 보게 되었다.
문제를 살펴보자.
문제
인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.
연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다.
일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다.
예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자.
이때, 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 곳이다. 아무런 벽을 세우지 않는다면, 바이러스는 모든 빈 칸으로 퍼져나갈 수 있다.
2행 1열, 1행 2열, 4행 6열에 벽을 세운다면 지도의 모양은 아래와 같아지게 된다.
바이러스가 퍼진 뒤의 모습은 아래와 같아진다.
벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다. 위의 지도에서 안전 영역의 크기는 27이다.
연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8)
둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다. 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다.
빈 칸의 개수는 3개 이상이다.
출력
첫째 줄에 얻을 수 있는 안전 영역의 최대 크기를 출력한다.
예제 입력은 아래 사이트에서 확인해보면 될것 같다.
https://www.acmicpc.net/problem/14502
14502번: 연구소
인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크
www.acmicpc.net
문제 접근 방법
이번문제의 가장 핵심은 벽을 어디다가 설치해야하냐이다.
나는 벽을 어디에 어떻게 설치해야할지 고민을 엄청 했다.
그래서 내 스스로 어떤 방법으로 벽을 설치해야하는지 여러 방법을 생각해봤는데 규칙을 찾지 못했다.
하지만 이번 문제의 답을 확인해보니 이번 문제는 일단 3개의 벽을 만들수 있는 모든 조합을 구하고
해당 조합에서의 바이러스를 퍼트려 안전구역을 구한후 최대값을 수정하는것이였다.
따라서 이번 문제는 아래와 같은 방식으로 접근을 해야한다.
1. 3개의 벽이 나올수 있는 방법은 DFS로 구한다.
2. DFS로 벽의 조합을 구했다면 해당 조합으로 바이러스를 퍼트려 안전구역을 구한다.
3. 구한 안전구역의 수를 가지고 최대값을 업데이트 한다.
그래서 나는 1번의 경우에는 아래와 같이 구했다.
1. 3개의 벽이 나올수 있는 방법은 DFS로 구한다.
private void dfs(int count) {
// TODO Auto-generated method stub
if(count > 3) {
bfs();
return;
}else {
for(int i = 0;i<height;i++) {
for(int j = 0; j<width;j++) {
if(map[i][j] == 0) { // 빈공간일때 접근
map[i][j] = 1; //해당 부분에 벽을 세우고
dfs(count+1); //+1을 해줌
map[i][j] = 0;// 해당 부분에서 안전지역 구하고 초기화 시켜줘야지 다른 조합구함
}
}
}
}
}map[i][j]에다가 벽을 만들고 count+1을 해준뒤 재귀 호출 하여서 벽의 개수가 3이하라면 벽을 다시 만들어줬다.
벽의 개수가 3개 이상이면 BFS를 통해서 안전구역을 구한다.
그리고 안전구역을 구하고 나면 만들었던 벽을 없애고 다른곳에 벽을 만들어서 다른 조합을 구한다.
2. DFS로 벽의 조합을 구했다면 해당 조합으로 바이러스를 퍼트려 안전구역을 구한다.
3. 구한 안전구역의 수를 가지고 최대값을 업데이트 한다.
private void bfs() {
// TODO Auto-generated method stub
int[] dx = {1,0,-1,0};
int[] dy = {0,1,0,-1};
int[][] temp = new int[height][width];
//저장되어 있는 map을 clone해서 복제한것에서 바이러스를 퍼뜨림
for(int i = 0; i<height;i++) {
for(int j = 0; j<width;j++) {
temp[i][j] = map[i][j];
}
}
Queue<Virus> que = new LinkedList<>();
//모든 바이러스의 위치를 Queue에 담음
for(int i = 0;i<height;i++) {
for(int j = 0;j<width;j++) {
if(temp[i][j] == 2) {
que.add(new Virus(i,j));
}
}
}
//Queue에 있는 바이러스위치들을 뽑아서 뻗을수 있는 모든 위치를 접근
while(!que.isEmpty()) {
Virus v = que.poll();
for(int i = 0;i<dx.length;i++) {//위,아래,양옆에 접근
int xx = v.x+dx[i];
int yy = v.y+dy[i];
if(xx>-1&& yy>-1 && xx<height && yy<width) {
if(temp[xx][yy] == 0) { //빈공간이라면 진입
temp[xx][yy] = 2; //바이러스 감염시키고
que.add(new Virus(xx,yy)); //큐에 집어 넣는다.
}
}
}
}
int count = 0;
for(int i = 0; i<height;i++) {
for(int j = 0; j<width;j++) {
if(temp[i][j] == 0)
count++;
}
}
if(count > max)
max = count;
}
}위에선 이제 받은 map을 가지고 바이러스를 퍼트려야 하는데 여기서 중요한 점은 바이러스를 퍼트릴땐
map을 복사한 배열에다가 바이러스를 퍼트려야 한다.
그래야지만 다른 조합을 구할수 있기 때문이다.
(clone() 함수는 2차원 배열에서는 먹히지 않는다. 따라서 따로 구현을 해줘야 한다.)
배열을 복사를 완료 했다면 이제 복사한 배열에서 바이러스를 가지고 있는 위치를 Queue에 모두 담아야한다.
그렇게 해야지만 모든 부분에 바이러스를 퍼트릴수 있기 때문이다.
이제 복사한 배열로 바이러스를 모두 퍼트렸다면 안전한 구역이 나왔을텐데
나온 안전한 구역의 개수를 가지고 최대값을 수정해주면 안전한 구역의 최대값은 계속해서 업데이트가 된다.
위 3단계를 모두 합친 전체 소스는 아래와 같다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
public class Run {
int height;
int width;
int[][] map;
int max;
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
Run a = new Run();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] temp = br.readLine().split(" ");
a.height = Integer.parseInt(temp[0]);
a.width = Integer.parseInt(temp[1]);
//map에 값 입력
a.map = new int[a.height][a.width];
for(int i = 0;i<a.height;i++) {
String[] nums = br.readLine().split(" ");
for(int j = 0; j<nums.length;j++) {
a.map[i][j] = Integer.parseInt(nums[j]);
}
}
System.out.println(a.findSafeArea());
}
private int findSafeArea() {
// TODO Auto-generated method stub
dfs(1);
return max;
}
private void dfs(int count) {
// TODO Auto-generated method stub
if(count > 3) {
bfs();
return;
}else {
for(int i = 0;i<height;i++) {
for(int j = 0; j<width;j++) {
if(map[i][j] == 0) { // 빈공간일때 접근
map[i][j] = 1; //해당 부분에 벽을 세우고
dfs(count+1); //+1을 해줌
map[i][j] = 0;// 해당 부분에서 안전지역 구하고 초기화 시켜줘야지 다른 조합구함
}
}
}
}
}
private void bfs() {
// TODO Auto-generated method stub
int[] dx = {1,0,-1,0};
int[] dy = {0,1,0,-1};
int[][] temp = new int[height][width];
//저장되어 있는 map을 clone해서 복제한것에서 바이러스를 퍼뜨림
for(int i = 0; i<height;i++) {
for(int j = 0; j<width;j++) {
temp[i][j] = map[i][j];
}
}
Queue<Virus> que = new LinkedList<>();
//모든 바이러스의 위치를 Queue에 담음
for(int i = 0;i<height;i++) {
for(int j = 0;j<width;j++) {
if(temp[i][j] == 2) {
que.add(new Virus(i,j));
}
}
}
//Queue에 있는 바이러스위치들을 뽑아서 뻗을수 있는 모든 위치를 접근
while(!que.isEmpty()) {
Virus v = que.poll();
for(int i = 0;i<dx.length;i++) {//위,아래,양옆에 접근
int xx = v.x+dx[i];
int yy = v.y+dy[i];
if(xx>-1&& yy>-1 && xx<height && yy<width) {
if(temp[xx][yy] == 0) { //빈공간이라면 진입
temp[xx][yy] = 2; //바이러스 감염시키고
que.add(new Virus(xx,yy)); //큐에 집어 넣는다.
}
}
}
}
int count = 0;
for(int i = 0; i<height;i++) {
for(int j = 0; j<width;j++) {
if(temp[i][j] == 0)
count++;
}
}
if(count > max)
max = count;
}
}
class Virus{
int x;
int y;
public Virus(int x, int y) {
super();
this.x = x;
this.y = y;
}
}
느낀점
1. 딱히 어떤 규칙으로 조합을 만들어 낼수가 없다면 완전 탐색으로 모든 조합을 만들어봐라.
2. BFS를 할때 시작점이 딱히 없다면 queue에 넣어야 하는 값들을 한꺼번에 넣고 시작해라.
3. clone() 함수는 2차원 배열까지 깊은 복사를 해주지 않으니 2차원 배열을 깊은 복사를 하고 싶으면
직접 구현해야 한다.
'코딩일기 > 알고리즘' 카테고리의 다른 글
| [백준 1789 : 실버5] 수들의 합 ( 그리디 / Java ) (0) | 2021.08.05 |
|---|---|
| [백준 1932번 : 실버1] 정수 삼각형 ( DP / Java ) (0) | 2021.08.05 |
| [백준 11724번 : 실버2] 연결 요소의 개수 ( DFS / Java) (0) | 2021.08.05 |
| [백준 1946번 : 실버 1] 신입사원 ( 그리디 / Java) (0) | 2021.08.05 |
| [백준 2579번 : 실버3] 계단오르기 (DP / Java) (0) | 2021.08.04 |
