BOJ_14502_연구소

1

구분: 그래프 이론, 그래프 탐색, 부르트포스 알고리즘, 너비 우선 탐색

언어: Java
전략:

1. 벽을 세울 빈칸 3개를 조합을 이용해서 선택한다. 

- 벽은 3개만 세울 수 있으니까 3개만 만듬

- 빈칸들 중 3개를 선택한다. 

2. 조합이 완성되면 그 곳에 벽을 세우고, 바이러스를 퍼트린다. 

- BFS를 이용하여 전체를 다 탐색하면서 바이러스를 퍼트린다.

3. 안전 영역의 넓이를 구한다.

- 바이러스가 퍼지지 않은 부분(0)의 면적(개수)을 구한다.

 

---

2. 코드

import java.util.ArrayList;
import java.util.Scanner;
import java.util.Queue;
import java.util.LinkedList;

public class Main {

	static int w, h;//가로, 세로
	static int[][] map, mapcopy;//맵과 맵 복사본
	static ArrayList<Node> walls, virus;//벽과 바이러스를 담을 에레이리스트
	static int[] comb;//조합을 담을 배열
	//4방 탐색
	static int[] dx = {1, -1, 0, 0};
	static int[] dy = {0, 0, 1, -1};
	
	static int maxarea = Integer.MIN_VALUE;
	//좌표를 담을 자료구조
	static class Node{
		int y, x;
		Node(int y, int x){
			this.x = x;
			this.y = y;
		}
	}
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		h = scanner.nextInt();
		w = scanner.nextInt();
		walls = new ArrayList<>();
		virus = new ArrayList<>();
		comb = new int[3];//벽은 딱 3개
		
		map = new int[h][w];
		for(int i = 0; i<h; i++) {
			for(int j = 0; j<w; j++) {
				map[i][j] = scanner.nextInt();
				
				if(map[i][j]==0) {//벽이라면 벽에 넣는다.
					walls.add(new Node(i, j));
				}
				else if(map[i][j] == 2) {//바이러스라면 바이러스에 넣는다.
					virus.add(new Node(i, j));
				}
				
			}
		}
		
		combination(0,0);
		System.out.println(maxarea);
		

	}//main
	
	//벽을 세울 위치 조합 만드는 함수 
	private static void combination(int cnt, int start) {
		if(cnt ==3) {
			spreadVirus();
			int nowarea = safeArea(mapcopy);
			//최대 면적 고른다.
			maxarea = Math.max(maxarea, nowarea);
			
			return;
		}
		//조합을 생성하는 중
		for(int i = start; i<walls.size(); i++) {
			comb[cnt] = i;
			combination(cnt+1, i+1);
		}
	}//combination
	
	//바이러스의 퍼짐을 구하는 함수 
	private static void spreadVirus() {
		//원본 지도를 복제한다(원래는 계속 사용해야 하기 떄문에)
		mapcopy = new int[h][w];
		for(int i = 0; i<h; i++) {
			for(int j = 0; j<w; j++) {
				mapcopy[i][j] = map[i][j];
			}
		}
		 
		//벽 세우기
		for(int i = 0; i<3; i++) {
			Node node = walls.get(comb[i]);
			mapcopy[node.y][node.x] = 1;
		}
		
		//바이러스 퍼트리기
		Queue<Node> q = new LinkedList<>();
		
		for(int i = 0; i<virus.size(); i++) {
			Node node = virus.get(i);
			q.add(node);
		}
		
		while(!q.isEmpty()) {
			Node node = q.poll();
			int qx = node.x;
			int qy = node.y;
			
			for(int d = 0; d<4; d++) {
				int nx = qx + dx[d];
				int ny = qy + dy[d];
				
				//범위 탐색
				if(nx<0||ny<0||nx>=w||ny>=h)
					continue;
				//벽이거나 이미 바이러스면 지나가 
				if(mapcopy[ny][nx]!=0)
					continue;
				//빈칸을 바이러스로 만들어
				mapcopy[ny][nx] = 2;
				q.add(new Node(ny, nx));
			}
		}
	}//virus
	
	
	//안전 영역을 구하는 함수
	private static int safeArea(int[][] arr) {
		int area = 0;
		for(int i = 0; i<h; i++) {
			for(int j = 0; j<w; j++) {
				//바이러스가 안퍼진 공간들을 다 더한다. 
				if(arr[i][j] == 0) {
					area++;
				}
			}
		}
		return area;
	}//safearea

}

---

3

부르트포스와 BFS를 동시에 접할 수 있는 좋은 문제다.

예전에 시도했을떄는 풀지 못하였는데, 이제는 풀 수 있어서 기분이 좋다.