[BaekJoon] 14502 연구소

1.  문제 링크

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

2.  문제

요약

• N X M 크기의 직사각형으로 연구소를 나타낼 수 있고 직사각형은 1 X 1 크기의 정사각형으로 나누어져 있습니다.
• 연구소는 빈 칸, 벽으로 이루어져 있고 벽은 칸 하나를 차지합니다.
• 일부 칸은 바이러스가 존재하고, 바이러스는 인접한 상하좌우로 퍼져나갈 수 있으며, 새로 3개의 벽을 세워야 합니다.
• 벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 하는데 얻을 수 있는 안전 영역 크기의 최댓값을 구하는 문제입니다.
• 입력: 첫 번째 줄에 3보다 크거나 같고 8보다 작거나 같은 지도의 세로 크기 N과 가로 크기 M이 주어지고 두 번째 줄부터 N개의 줄에는 지도의 모양이 주어집니다.
  • 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치를 의미하고 2의 개수는 2보다 크거나 같고 10보다 작거나 같은 자연수입니다.
• 출력: 첫 번째 줄에 얻을 수 있는 안전 영역의 최대 크기를 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
	static int[][] map;
	static int maxArea;
	public void findMaxArea(int wallNum) {
		if(wallNum == 3) {
			bfs();
			return;
		}
		for(int i = 0; i < map.length; i++) {
			for(int j = 0; j < map[i].length; j++) {
				if(map[i][j] == 0) {
					map[i][j] = 1;
					findMaxArea(wallNum + 1);
					map[i][j] = 0;
				}
			}
		}
	}
	
	public void bfs() {
		Queue<Point> queue = new LinkedList<Point>();
		for(int i = 0; i < map.length; i++) {
			for(int j = 0; j < map[i].length; j++) {
				if(map[i][j] == 2) {
					queue.offer(new Point(i, j));
				}
			}
		}
		int[][] copy = new int[map.length][map[0].length];
		for(int i = 0; i < map.length; i++) {
			copy[i] = map[i].clone();
		}
		int[] dx = {-1, 0, 1, 0};
		int[] dy = {0, -1, 0, 1};
		while(!queue.isEmpty()) {
			Point cur_point = queue.poll();
			for(int i = 0; i < 4; i++) {
				int cx = cur_point.x + dx[i];
				int cy = cur_point.y + dy[i];
				if(cx >= 0 && cx < map.length && cy >= 0 && cy < map[0].length) {
					if(copy[cx][cy] == 0) {
						copy[cx][cy] = 2;
						queue.offer(new Point(cx, cy));
					}
				}
			}
		}
		findSafeArea(copy);
	}
	
	public void findSafeArea(int[][] copy) {
		int num = 0;
		for(int i = 0; i < copy.length; i++) {
			for(int j = 0; j < copy[i].length; j++) {
				if(copy[i][j] == 0) {
					num++;
				}
			}
		}
		maxArea = maxArea < num ? num : maxArea;
	}
	
	public void getMaxArea() {
		maxArea = 0;
		findMaxArea(0);
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String[] input = br.readLine().split(" ");
		int row = Integer.parseInt(input[0]);
		int col = Integer.parseInt(input[1]);
		map = new int[row][col];
		for(int i = 0; i < row; i++) {
			input = br.readLine().split(" ");
			for(int j = 0; j < col; j++) {
				map[i][j] = Integer.parseInt(input[j]);
			}
		}
		br.close();
		Main m = new Main();
		m.getMaxArea();
		bw.write(maxArea + "\n");
		bw.flush();
		bw.close();
	}
	
	public static class Point {
		int x, y;
		public Point(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
}

4.  접근

• 해당 문제는 DFS, BFS를 이용하여 해결할 수 있습니다.
• 3개의 벽을 세우는 위치를 DFS를 통해 구하고 3개의 벽을 세운 후에 안전 영역을 구할 때 BFS를 이용하여 구합니다.
• 직사각형의 모든 정사각형을 돌면서 해당 위치가 빈 칸이라면 해당 위치에 벽을 세우고 재귀함수 호출을 통해 다른 빈 칸을 찾아 벽을 세우고 이렇게 세운 벽이 세 칸이라면 그 때의 안전 영역의 크기를 구합니다.
• 안전 영역의 크기를 구한 이후에는 벽을 세운 위치를 빈칸으로 만들고 다른 경우의 수로 벽을 세운 후에 안전 영역의 크기를 구하며 안전 영역의 최대 크기를 구합니다.

public void findMaxArea(int wallNum) {
	if(wallNum == 3) {
		bfs();
		return;
	}
	for(int i = 0; i < map.length; i++) {
		for(int j = 0; j < map[i].length; j++) {
			if(map[i][j] == 0) {
				map[i][j] = 1;
				findMaxArea(wallNum + 1);
				map[i][j] = 0;
			}
		}
	}
}

• 안전 영역을 구할 때는 BFS를 이용합니다.
• 바이러스가 있는 위치들을 Queue에 넣어두고 바이러스가 있는 위치의 상하좌우 위치를 확인하여 해당 위치가 직사각형 내에 있고 빈 칸이라면 해당 위치를 바이러스가 있는 칸으로 변경하고 해당 위치의 상하좌우도 확인하기 위해 해당 위치 또한 Queue에 넣어줍니다.
• BFS를 통해 바이러스가 있는 위치로 변할 수 있는 모든 칸을 변경한 후에 전체 칸을 돌면서 빈 칸인 곳이 몇 개인지 세어주고 이전까지의 가장 컸던 안전 영역 크기와 비교하여 더 큰 크기로 안전 영역의 크기를 변경합니다.

public void bfs() {
	Queue<Point> queue = new LinkedList<Point>();
	for(int i = 0; i < map.length; i++) {
		for(int j = 0; j < map[i].length; j++) {
			if(map[i][j] == 2) {
				queue.offer(new Point(i, j));
			}
		}
	}
	int[][] copy = new int[map.length][map[0].length];
	for(int i = 0; i < map.length; i++) {
		copy[i] = map[i].clone();
	}
	int[] dx = {-1, 0, 1, 0};
	int[] dy = {0, -1, 0, 1};
	while(!queue.isEmpty()) {
		Point cur_point = queue.poll();
		for(int i = 0; i < 4; i++) {
			int cx = cur_point.x + dx[i];
			int cy = cur_point.y + dy[i];
			if(cx >= 0 && cx < map.length && cy >= 0 && cy < map[0].length) {
				if(copy[cx][cy] == 0) {
					copy[cx][cy] = 2;
					queue.offer(new Point(cx, cy));
				}
			}
		}
	}
	findSafeArea(copy);
}

1. 주어진 연구소의 상태를 2차원 배열 map에 넣어놓고 얻을 수 있는 안전 영역의 최대 크기를 나타내는 변수인 maxArea의 값을 0으로 초기화합니다.
2. DFS 알고리즘을 통해 세 칸의 벽을 세우고 그 때의 안전 영역의 크기를 구하여 얻을 수 있는 안전 영역의 최대 크기를 구합니다.
   1. 직사각형의 모든 칸을 돌면서 벽을 세웁니다.
      1. 만약 해당 칸의 값이 0이라면, 즉 빈 칸이라면 해당 칸의 값을 1로 변경하고 세운 벽의 개수를 1 증가시킨 후에 재귀호출을 진행합니다.
      2. 재귀호출이 끝난 후에는 해당 칸의 값을 0으로 변경하여 다시 빈 칸으로 만들어줍니다.
   2. 만약 wallNum의 값이 3이라면, 즉 세운 벽의 개수가 3이라면 그 때의 안전 영역의 크기를 구합니다.
      1. Queue를 생성하고 값이 2인 칸들을 Queue에 넣어줍니다.
      2. 현재 map의 값들을 copy라는 2차원 배열에 복사합니다.
      3. Queue가 비워지기 전까지 반복문을 돌며 바이러스가 있는 칸으로 변할 수 있는 칸들을 바이러스가 있는 칸으로 변경해줍니다.
         1. Queue에 있는 위치를 하나 빼주고 해당 위치의 상하좌우를 확인하여 해당 위치가 map 안에 존재하고 해당 위치의 값이 0이라면 해당 위치의 크기를 2로 변경해주고 해당 위치를 Queue에 넣어줍니다.
      4. 바이러스가 있는 칸으로 변할 수 있는 칸들을 바이러스가 있는 칸으로 변경해준 후에 그 때의 안전 영역의 크기를 구합니다.
         1. 안전 영역의 크기를 나타내는 변수 num을 생성하고 값을 0으로 초기화합니다.
         2. 직사각형의 모든 칸들을 돌면서 해당 칸의 값이 0이라면 num의 값을 1 증가시킵니다.
         3. 현재 maxArea 값과 num 값을 비교하여 더 큰 값을 maxArea 값으로 설정합니다.
3. maxArea의 값을 출력합니다.