[BAEKJOON] 연구소

---

0 - 안전 지역
1 - 벽
2 - 바이러스

 

우리의 목표는 3개의 벽을 세워 최대한 바이러스가 퍼지지 않게 해야 한다.

먼저 벽을 세울 수 있는 안전 지역 3 곳을 '조합' 하자.

조합이 이루어졌을 때마다 바이러스가 모두 퍼졌다 가정하고, 남은 안전 지역의 수를 세어 최댓값을 반환하면 된다.

 

문제 풀이 팁

1. 연구소 초기 상태를 입력 받아 저장할 때 바이러스의 위치, 안전 지역 위치를 각각의 리스트에 담는다.

  → 벽을 세울 위치 3 곳을 조합할 때 안전 지역(0)인지 확인하는 조건문 없어도 됨! 리스트에 담긴 위치에서만 3곳 조합하면 됨

2. 벽을 세울 위치 3곳을 조합했을 때의 연구소 상태에서 바이러스를 퍼뜨려본다. 그리고 남은 안전 지역 수를 센다. 안전 지역 수의 최댓값을 갱신한다.

1️⃣ 벽을 세울 곳 조합하기 ➡ DFS (재귀)

2️⃣ 바이러스 퍼뜨리기 ➡ BFS (큐)

주의할 점❗ 원본 배열 즉, 연구소 초기 상태는 변경하지 않아야 하기 때문에 배열의 깊은 복사 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;

public class Main {
	static int N, M;
	static int[][] arr, copyArr, dir = {{1,0}, {-1, 0}, {0,1}, {0, -1}};
	static ArrayList<Point> list = new ArrayList<>();
	static ArrayList<Point> virus = new ArrayList<>();
	static boolean visit[];
	static Queue<Point> queue = new LinkedList<>();
	static int answer;
	public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new int[N][M];
        for(int i=0; i<N; i++) {
        	st = new StringTokenizer(br.readLine());
        	for(int j=0; j<M; j++) {
        		arr[i][j] = Integer.parseInt(st.nextToken());
        		if(arr[i][j]==0)
        			list.add(new Point(i, j));
        		else if(arr[i][j] == 2) {
        			virus.add(new Point(i, j));
        			
        		}
        	}
        }
        
        // 3개 조합 만들기
        visit = new boolean[list.size()];
        copyArr = arr;
        comb(0, 0);
        System.out.println(answer);
	}
	
	private static void comb(int idx, int cnt) {
		if(cnt == 3) {
			// bfs
			bfs(arr);
			return;
		}
		for(int i=idx; i<list.size(); i++) {
			if(!visit[i]) {
				visit[i] = true;
				arr[list.get(i).x][list.get(i).y] = 1;
				comb(i+1, cnt+1);
				arr[list.get(i).x][list.get(i).y] = 0;
				visit[i] = false;
			}
		}
	}

	private static void bfs(int[][] copyArr) {
		int total_safe = 0;
		copyArr = new int[N][M];

		for (int i = 0; i < N; i++) {
			copyArr[i] = arr[i].clone();
		}

		for(Point v : virus) {
			queue.add(new Point(v.x, v.y));
		}
		
		while(!queue.isEmpty()) {
			Point now = queue.poll();
			int nowX = now.x;
			int nowY = now.y;
			
			for(int i=0; i<4; i++) {
				int nextX = nowX + dir[i][0];
				int nextY = nowY + dir[i][1];
				
				if(nextX>=0 && nextY>=0 && nextX<N && nextY<M && copyArr[nextX][nextY]==0) {
					// 바이러스 전염시키기
					copyArr[nextX][nextY] = 2;
					queue.add(new Point(nextX, nextY));
				}
			}
		}
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(copyArr[i][j] == 0) {
					total_safe++;
				}
			}
		}
		answer = Math.max(answer, total_safe);
	}

	public static class Point{
		int x,y;
		public Point(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
}

 

[출처]

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

14502번: 연구소