[백준] 14502번 : 연구소 - 자바[Java]

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

14502번: 연구소

풀이

연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구해야 한다. 즉, 최댓값을 구해야 하므로 벽 3개를 세울 수 있는 모든 경우의 수를 구해 그 중 안전 영역 크기의 최댓값을 구해야 한다.

 

문제를 풀기위해 전체 로직을 3단계로 나누었다.

 

1. 빈 칸 중 3개 선택(DFS/완전탐색)

2. 바이러스 전파(BFS or DFS)

3. 안전영역 크기 세기(이중 for문)

 

먼저 main 함수에서 연구소의 지도를 입력받은 후, 빈 칸 중 3개를 선택하여 벽을 세우는 기능을 하는 createWall(0)을 호출한다.

	private static int n, m;
	private static int maxSafeArea = Integer.MIN_VALUE;
	private static int[][] rooms;

    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());
    	
    	rooms = new int[n][m];
    	
    	for (int i = 0; i < n; i++) {
    		st = new StringTokenizer(br.readLine());
    		for (int j = 0; j < m; j++) {
    			rooms[i][j] = Integer.parseInt(st.nextToken());
    		}
    	}
    	
    	createWall(0);
    	
    	System.out.println(maxSafeArea);
    }

 

void createWall(int wall)

연구소의 빈 칸에 3개의 벽을 세운다. DFS를 사용하여 모든 경우의 수를 구하고, 3개의 벽을 세웠다면 countSafeArea()를 호출해 안전 영역의 크기를 구한다.

    private static void createWall(int wall) {
    	if (wall == 3) {
    		countSafeArea();
    		return;
    	}
    	
    	for (int i = 0; i < n; i++) {
    		for (int j = 0; j < m; j++) {
    			if (rooms[i][j] == 0) {
    				rooms[i][j] = 1;
    				createWall(wall+1);
    				rooms[i][j] = 0;
    			}
    		}
    	}
    }

 

void countSafeArea()

virus() 메서드를 호출하여 바이러스를 퍼지게 한 후, 이중 for 문을 사용하여 안전영역의 크기를 구하고, 이를 maxSafeArea와 비교하여 더 큰 값을 maxSafeArea에 저장한다.

    private static void countSafeArea() {
    	int[][] copyRooms = new int[n][m];
    	for (int i = 0; i < n; i++) {
    		copyRooms[i] = Arrays.copyOfRange(rooms[i], 0, m);
    	}
    	
    	for (int i = 0; i < n; i++) {
    		for (int j = 0; j < m; j++) {
    			if (copyRooms[i][j] == 2) {
    				virus(copyRooms, i, j);
    			}
    		}
    	}
    	
    	int cnt = 0;
    	for (int i = 0; i < n; i++) {
    		for (int j = 0; j < m; j++) {
    			if (copyRooms[i][j] == 0) {
    				cnt++;
    			}
    		}
    	}

    	maxSafeArea = Math.max(maxSafeArea, cnt);
    }

 

void virus(int[][] copyRooms, int r, int c)

BFS를 사용하여 바이러스를 전파한다.

    private static void virus(int[][] copyRooms, int r, int c) {
    	int[] dr = {-1, 0, 1, 0};
    	int[] dc = {0, 1, 0, -1};
    	Queue<int[]> positions = new LinkedList<>();
    	
    	positions.add(new int[]{r, c});
    	
    	while(!positions.isEmpty()) {
    		int[] cur = positions.poll();
    		
    		for (int i = 0; i < 4; i++) {
    			int nr = cur[0] + dr[i];
    			int nc = cur[1] + dc[i];
    			
    			if (checkIndex(nr, nc) && copyRooms[nr][nc] == 0) {
    				copyRooms[nr][nc] = 3;
    				positions.add(new int[]{nr, nc});
    			}
    		}
    	}
    }
    
    private static boolean checkIndex(int r, int c) {
    	return r >= 0 && r < n && c >= 0 && c < m;
    }

원래는 빈 칸(0)이었지만 바이러스가 전파된 칸은 3으로 변경하도록 했다. 2가 아니라 3으로 변경하는 이유는, countSafeArea()에서는 칸이 2인 경우에 virus() 메서드를 호출하기 때문에, 이미 바이러스가 퍼진 곳은 탐색할 필요가 없으므로 3으로 변경하여 쓸데없는 호출을 피하도록 하였다.

 

전체 코드

import java.io.*;
import java.util.*;

public class Main {
	
	private static int n, m;
	private static int maxSafeArea = Integer.MIN_VALUE;
	private static int[][] rooms;

    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());
    	
    	rooms = new int[n][m];
    	
    	for (int i = 0; i < n; i++) {
    		st = new StringTokenizer(br.readLine());
    		for (int j = 0; j < m; j++) {
    			rooms[i][j] = Integer.parseInt(st.nextToken());
    		}
    	}
    	
    	createWall(0);
    	
    	System.out.println(maxSafeArea);
    }
    
    private static void createWall(int wall) {
    	if (wall == 3) {
    		countSafeArea();
    		return;
    	}
    	
    	for (int i = 0; i < n; i++) {
    		for (int j = 0; j < m; j++) {
    			if (rooms[i][j] == 0) {
    				rooms[i][j] = 1;
    				createWall(wall+1);
    				rooms[i][j] = 0;
    			}
    		}
    	}
    }
   
    private static void countSafeArea() {
    	int[][] copyRooms = new int[n][m];
    	for (int i = 0; i < n; i++) {
    		copyRooms[i] = Arrays.copyOfRange(rooms[i], 0, m);
    	}
    	
    	for (int i = 0; i < n; i++) {
    		for (int j = 0; j < m; j++) {
    			if (copyRooms[i][j] == 2) {
    				virus(copyRooms, i, j);
    			}
    		}
    	}
    	
    	int cnt = 0;
    	for (int i = 0; i < n; i++) {
    		for (int j = 0; j < m; j++) {
    			if (copyRooms[i][j] == 0) {
    				cnt++;
    			}
    		}
    	}

    	maxSafeArea = Math.max(maxSafeArea, cnt);
    }
    
    private static void virus(int[][] copyRooms, int r, int c) {
    	int[] dr = {-1, 0, 1, 0};
    	int[] dc = {0, 1, 0, -1};
    	Queue<int[]> positions = new LinkedList<>();
    	
    	positions.add(new int[]{r, c});
    	
    	while(!positions.isEmpty()) {
    		int[] cur = positions.poll();
    		
    		for (int i = 0; i < 4; i++) {
    			int nr = cur[0] + dr[i];
    			int nc = cur[1] + dc[i];
    			
    			if (checkIndex(nr, nc) && copyRooms[nr][nc] == 0) {
    				copyRooms[nr][nc] = 3;
    				positions.add(new int[]{nr, nc});
    			}
    		}
    	}
    }
    
    private static boolean checkIndex(int r, int c) {
    	return r >= 0 && r < n && c >= 0 && c < m;
    }
}