[백준 14502] 연구소

[문제 바로가기]👇

14502번: 연구소

 

 

풀이

안전 영역의 최댓값을 구하는 문제이기 때문에 문제에서 제시한 내용에 따라 구현을 하면 답을 찾을 수 있다.

문제의 내용(진행 흐름)을 정리하고 이 순서에 따라 메서드를 구현해 진행했다

문제 내용 정리

1. 연구소 안에 벽을 3개 세워야 한다
   1-1. 벽을 세울 위치를 정했다면 3개를 놓는다
2. 바이러스가 상하좌우 인접한 빈 칸으로 퍼진다
3. 바이러스가 퍼진 뒤 안전 영역(바이러스가 퍼질 수 없는 곳) 크기를 계산한다

 

1. 입력 받기

연구소 정보를 받으면서 빈 칸인 곳을 list에 저장을 해 나중에 벽을 세울 곳을 완전 탐색으로 찾을 때 쉽게 찾을 수 있도록 했다

	static int[] dr = {-1,0,1,0}; // 상우하좌
	static int[] dc = {0,1,0,-1}; // 상우하좌
	
	static int[] res; // 조합 결과 저장
	static int N, M, maxSafeArea;
	static int[][] map, temp; // 연구소 정보 저장, 임시 테이블
	static boolean[][] v; // bfs 탐색시 방문 체크
	static List<int[]> list; // 연구소 중 빈 칸인 위치 저장
	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]; // 연구소 정보 저장
		temp = new int[N][M]; // 임시 테이블
		list = new ArrayList<>(); // 연구소 중 빈 칸인 위치 저장
		
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for(int j=0; j<M; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if(map[i][j]==0) list.add(new int[] {i,j}); // 빈 칸이면 list에 저장
			}
		}
		

		br.close();
	}

 

 

2. 연구소 안에 벽을 세울 위치 정하기 - 조합

벽을 세운다

• 빈 칸에에만 세울 수 있음
• 어디에 어떤 벽을 세우든지 같음 >> 순서 상관 X
• 반드시 3개를 세워야 함

>> 빈 칸에서 3개를 고르는 조합!

 

조합 코드를 활용해 빈칸을 저장한 list의 크기만큼 돌면서 list의 인덱스를 저장했다

하나의 조합이 완성 됐을 때, 벽을 놓고, 바이러스를 확산 시키고, 안전 영역의 크기를 계산해서 벽을 세우는 하나의 경우에 대해서 안전 영역의 최댓값을 갱신해줘야 한다

그렇기 때문에 완성된 조합으로 벽을 놓을 때 원본 배열이 손상되지 않게 하기 위해 원본 배열을 복사한 temp 배열에 벽을 놓고 다음 단계들을 진행한다

 

// 1.벽을 놓을 위치 정하기 - 조합
res = new int[3];
solution(0,0);

static void solution(int cnt, int start) {
		if(cnt == 3) { // 조합 완성		
			//temp 초기화
			for(int i=0; i<N; i++) {
				for(int j=0; j<M; j++) temp[i][j] = map[i][j];
			}
			
			// 2. 정한 위치에 벽 놓기
			for(int i=0; i<3; i++) {
				int[] pos = list.get(res[i]);
				int wr = pos[0], wc = pos[1];
				temp[wr][wc] = 1;
			}
			
			// 3. 바이러스 확산		
			
			// 4. 안전 영역 크기 계산
			return;
		}
		
		for(int i=start; i<list.size(); i++) {
			res[cnt] = i;
			solution(cnt+1, i+1);
		}
}

 

3. 바이러스 확산

바이러스는 인접한 4방향으로 확산하기 때문에 바이러스가 있는 곳에서 bfs로 탐색 한다

temp 배열을 사용한 이유처럼 매번 새로운 벽을 세울 때마다 방문 체크 배열을 새롭게 생성해준다

v = new boolean[N][M];
spread();

static void spread() {
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(!v[i][j] && temp[i][j]==2) bfs(i,j);
			}
		}
	}
	
static void bfs(int r, int c) {
		ArrayDeque<int[]> q = new ArrayDeque<>();
		v[r][c] = true;
		q.offer(new int[] {r, c});
		
		while(!q.isEmpty()) {
			int[] cur = q.poll();
			
			for(int d=0; d<4; d++) {
				int nr = cur[0] + dr[d];
				int nc = cur[1] + dc[d];
				
				if(0<=nr&&nr<N && 0<=nc&&nc<M && !v[nr][nc] && temp[nr][nc]==0) {
					v[nr][nc] = true;
					temp[nr][nc] = 2;
					q.offer(new int[] {nr,nc});
				}
			}
		}
}

 

 

4. 안전 영역 크기 계산

바이러스 확산이 끝났을 때, 전체 영역에서 0인 위치를 계산해 안전 영역의 크기를 구한다

maxSafeArea = Math.max(maxSafeArea, calSafeArea());

static int calSafeArea() { // 안전 영역 크기 계산 - 0인 위치 개수 세기
		int area = 0;
		for(int[] t : temp) {
			for(int val : t) if(val==0) area++;
		}
		return area;
	}

 

전체 코드

package Day_0330;

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

public class B14502 {
	static int[] dr = {-1,0,1,0}; // 상우하좌
	static int[] dc = {0,1,0,-1}; // 상우하좌
	
	static int[] res;
	static int N, M, maxSafeArea;
	static int[][] map, temp;
	static boolean[][] v;
	static List<int[]> list;
	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];
		temp = new int[N][M];
		list = new ArrayList<>();
		
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for(int j=0; j<M; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if(map[i][j]==0) list.add(new int[] {i,j});
			}
		}
		
		// 1.벽을 놓을 위치 정하기 - 조합
		res = new int[3];
		maxSafeArea = Integer.MIN_VALUE;
		solution(0,0);
		
		System.out.println(maxSafeArea);
		br.close();
	}
	
	static void solution(int cnt, int start) {
		if(cnt == 3) {
			//temp 초기화
			for(int i=0; i<N; i++) {
				for(int j=0; j<M; j++) temp[i][j] = map[i][j];
			}
			
			// 2. 정한 위치에 벽 놓기
			for(int i=0; i<3; i++) {
				int[] pos = list.get(res[i]);
				int wr = pos[0], wc = pos[1];
				temp[wr][wc] = 1;
			}
			
			// 3. 바이러스 확산 - bfs
			v = new boolean[N][M];
			spread();
			
			
			// 4. 안전 영역 크기 계산
			maxSafeArea = Math.max(maxSafeArea, calSafeArea());
			return;
		}
		
		for(int i=start; i<list.size(); i++) {
			res[cnt] = i;
			solution(cnt+1, i+1);
		}
	}
	
	static void spread() {
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(!v[i][j] && temp[i][j]==2) bfs(i,j);
			}
		}
	}
	
	static void bfs(int r, int c) {
		ArrayDeque<int[]> q = new ArrayDeque<>();
		v[r][c] = true;
		q.offer(new int[] {r, c});
		
		while(!q.isEmpty()) {
			int[] cur = q.poll();
			
			for(int d=0; d<4; d++) {
				int nr = cur[0] + dr[d];
				int nc = cur[1] + dc[d];
				
				if(0<=nr&&nr<N && 0<=nc&&nc<M && !v[nr][nc] && temp[nr][nc]==0) {
					v[nr][nc] = true;
					temp[nr][nc] = 2;
					q.offer(new int[] {nr,nc});
				}
			}
		}
	}
	
	static int calSafeArea() { // 안전 영역 크기 계산 - 0인 위치 개수 세기
		int area = 0;
		for(int[] t : temp) {
			for(int val : t) if(val==0) area++;
		}
		return area;
	}

}