[BOJ] 백준 14502번 연구소 (Java)

#14502 연구소

난이도 : 골드 5

유형 : 그래프 탐색/ 브루트포스/ BFS

14502번: 연구소

▸ 문제

▸ 입력

첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8)

둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다. 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다.

빈 칸의 개수는 3개 이상이다.

▸ 출력

첫째 줄에 얻을 수 있는 안전 영역의 최대 크기를 출력한다.

 

 

 

문제 풀이 

주어진 맵에 벽 3개를 브루트포스에서 모든 경우로 다 세워본 다음에 바이러스를 퍼트려보고 거기서 가장 안전 영역이 최대인 값을 출력해주면 된다. BFS와 backtracking에 대한 개념이 있다면 차근차근 설계하면 된다.

 

📚 조건

• 바이러스는 상하좌우 인접한 빈 칸으로 모두 퍼져나간다.
• 새로 세울 수 있는 벽은 3개 (꼭 3개 세워야 함)

 

구상

 1. 벽 3개를 가능한 모든 조합으로 벽을 세운다.

 2. 1번에서 만든 모든 맵을 깊은 복사하여 BFS탐색을 통하여 바이러스를 퍼트린다.

    > 깊은 복사 : 복사된 맵을 값을 변경해도 원본은 변경안됨.

 3. 각 2번의 결과를 카운트하여 안전영역(빈칸)의 갯수를 출력한다.

 

스케치

로직 1. 벽 3개를 모든 경우의 수로 세우기

Map에 백트래킹을 사용하여 벽 3개를 모든 경우의 수로 세워본다.  재귀 stack방식을 사용하여 벽이 3개가 세워졌으면 특정 연산을 실행(로직2)한 다음 제일 마지막에 들어간 부분을 리턴하고 다른 경우의 수의 맵을 또 만드는 방식이다.

// Backtracking : 벽3개 세우기 
static void makeWall(int start, int wallNum) {
	if(wallNum == 3) {
		return;
	}
	for(int i=start; i< n*m; i++) {
		int x = i/m;
		int y = i%m;
		
		if(map[x][y] ==0) {
			map[x][y] =1;
			makeWall(i+1, wallNum+1);
			map[x][y] =0;
		}
	}
}

 

로직 2.  깊은 복사한 맵에 바이러스 퍼트리기 BFS

1번에서 만든 벽 3개를 세운 맵을 깊은 복사하여(원본 값 변경 x) 바이러스를 퍼트린다. 해당 문제는 바이러스의 감염 속도를 조사하는 것은 아니기 때문에 따로 싸이클을 동시에 돌리거나 퍼지는 시간을 카운트 해주지 않아도 된다.

// Backtracking : 벽3개 세우기 
static void makeWall(int start, int wallNum) {

	if(wallNum == 3) {
		// map 복사
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				testMap[i][j] = map[i][j];
			}
		}
		
		for(Pos pos : virus) {
			bfs(pos.x, pos.y);
		}
		
		max = Math.max(max, getSafeSize());
		return;
	}
	
	for(int i=start; i< n*m; i++) {
		int x = i/m;
		int y = i%m;
		
		if(map[x][y] ==0) {
			map[x][y] =1;
			makeWall(i+1, wallNum+1);
			map[x][y] =0;
		}
	}
}

// bfs: virus 퍼트리기
static void bfs(int x, int y) {
	for(int i=0; i<4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		
		if(nx <0 || ny <0 || nx>n-1 || ny>m-1) continue;
		
		if(testMap[nx][ny] ==0) {
			testMap[nx][ny] =2;
			bfs(nx,ny);
		}
	}
}

 

로직 3. 안전 영역 크기 구하기

마지막으로 바이러스가 모두 퍼진 각 testMap의 안전영역의 크기를 조사하여 최댓값을 출력해주면 된다.

static int getSafeSize() {
	int size =0;
	for(int i=0; i<n; i++) {
		for(int j=0; j<m; j++) {
			if(testMap[i][j] ==0) {
				size++;
			}
		}
	}
	return size;
}

 

풀이 코드 

import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
	
	static int n,m;
	static int[][] map;
	static int[][] testMap;
	static List<Pos> virus;
	static int[] dx = {1, -1, 0, 0};
	static int[] dy = {0, 0, 1, -1};
	static int max =-1;
	
	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());
		
		map = new int[n][m];
		testMap = new int[n][m];
		virus = new ArrayList<>();
		
		for(int i=0; i<n; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<m; j++) {
				int num = Integer.parseInt(st.nextToken());
				map[i][j] = num;
				if(num ==2) {
					virus.add(new Pos(i,j));
				}
			}
		}
		
		makeWall(0,0);
		System.out.println(max);
		
	}
	
	// backtracking: 벽3개 세우기 
	static void makeWall(int start, int wallNum) {
	
		if(wallNum == 3) {
			// map 복사
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					testMap[i][j] = map[i][j];
				}
			}
			
			for(Pos pos : virus) {
				bfs(pos.x, pos.y);
			}
			
			max = Math.max(max, getSafeSize());
			return;
		}
		
		// 숫자를 0 ~ n*m 까지 증가시킬때 (i/m, i%m) 을 좌표로 하면 2차원 배열의 모든 인덱스를 탐색
		for(int i=start; i< n*m; i++) {
			int x = i/m;
			int y = i%m;
			
			if(map[x][y] ==0) {
				map[x][y] =1;
				makeWall(i+1, wallNum+1);
				map[x][y] =0;
			}
		}
	}
	
	
	// bfs: virus 퍼트리기
	static void bfs(int x, int y) {
		for(int i=0; i<4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			if (0 <= nx && nx < n && 0 <= ny && ny < m) {
				if(testMap[nx][ny] ==0) {
					testMap[nx][ny] =2;
					bfs(nx,ny);
				}
			}
		}
	}
	
	static int getSafeSize() {
		int size =0;
		for(int i=0; i<n; i++) {
			for(int j=0; j<m; j++) {
				if(testMap[i][j] ==0) {
					size++;
				}
			}
		}
		return size;
	}
}
class Pos {
	int x;
	int y;
	public Pos(int x, int y) {
		this.x =x;
		this.y =y;
	}
}