[백준] 14502번 연구소

www.acmicpc.net/problem/14502

14502번: 연구소

문제 설명 :

2차원 배열에서 0은 빈칸, 1은 벽, 2는 바이러스 일 때 벽을 3개 세운 뒤 바이러스를 퍼지지 않은 안전 영역 크기의 최댓값을 구하기

 

문제 풀이 : 

완전탐색으로 벽을 3개 세우고, 바이러스를 퍼뜨린 후, 안전 영역 중 최댓값을 구하면 됩니다.

 

2차원 배열 백트래킹으로 벽을 세워주기 위해 wall() 함수를 사용합니다.

3개의 벽을 조합하여 한 번 세웠을 때마다 safe()라는 함수로 갑니다.

safe() 함수에서는 map 배열을 복사하여 dfs를 활용해 바이러스를 퍼뜨립니다.

이후 안전영역 개수를 세줍니다.

이 과정을 반복하여 최종적으로는 answer 변수에 최대 안전영역 개수를 구해줍니다.

import java.util.Scanner;

public class Main {
	static int N, M, answer = Integer.MIN_VALUE;
	static int[][] map, copy_map;
	static boolean[][] visited;
	static int[][] dir = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		map = new int[N][M];
		copy_map = new int[N][M];

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				map[i][j] = sc.nextInt();
			}
		}

		wall(0, 0, 0);

		System.out.println(answer);

	}

	public static void wall(int x, int y, int cnt) {
		// 벽을 3개 세우면 안전영역 구하기
		if(cnt == 3) {
			safe();
			return;
			
		}
		// 벽 세우기
		else {
			//y가 범위 넘으면 
			if(y>=M) {
				wall(x+1,0,cnt);
				return;
			}
			//x가 범위 넘으면 끝
			if(x>=N) return;
			//세울 수 있다면
			if(map[x][y] == 0) {
				map[x][y] = 1;
				wall(x,y+1,cnt+1);
				map[x][y] = 0;// 하나의 벽을 세워 재귀가 끝났으면 다시 벽을 0으로 만든다.
			}
			//세울 벽이 없다면
			wall(x,y+1,cnt);
		}
	}

	public static void safe() {
		visited = new boolean[N][M];
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				copy_map[i][j] = map[i][j]; // 벽 세운 배열 복사
			}
		}
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if(copy_map[i][j] == 2) // dfs로 바이러스 퍼뜨리기
					dfs(i,j);
			}
		}
		
		int safe_area = 0; 
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if(copy_map[i][j] == 0) safe_area++; // 안전영역 개수 세주기
			}
		}
		
		answer = Math.max(answer, safe_area);// 최대 안전영역 개수
	}

	public static void dfs(int x, int y) {
		visited[x][y] = true;
		
		for (int i = 0; i < 4; i++) {
			int nx = x + dir[i][0];
			int ny = y + dir[i][1];
			
			if(isInside(nx,ny) && copy_map[nx][ny] == 0 && !visited[nx][ny]) {
				copy_map[nx][ny] = 2;
				dfs(nx,ny);
			}
		}
	}

	public static boolean isInside(int x, int y) {
		return x>=0 && x<N && y>=0 && y<M;
	}

}