[백준] JAVA - 14502. 연구소

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

14502번: 연구소

생각

벽 3개를 완전탐색 3형제 중 조합을 통해 세워줬습니다. 벽 3개를 모두 세운 다음 각각의 경우마다 안전 영역의 크기가 최대값을 찾는 문제입니다.

 

벽을 세울때 재귀함수를 사용하여 현재위치에 벽을 세울 수 있다면 벽을 세워주고 그 다음 단계로 들어가 세울 수 있는 모든 경우를 탐색한뒤, 세웠던 벽을 원래대로 복구시켜줍니다.

 

벽을 모두 세운 다음 BFS를 사용하여 바이러스가 퍼지는 함수 spread를 만들었습니다. BFS 에서 바이러스의 좌표를 모두 큐에 넣어준다음 큐의 사이즈만큼 반복문을 다시 돌아 각 step 별로 바이러스가 동일 시간에 퍼져나가게끔 구현했습니다. 이때 2차원 배열을 copy하여 바이러스가 퍼진곳을 마킹했습니다.

 

copyMap 을 모두 돌며 안전영역을 카운트한뒤 가장 큰 안전영역을 찾아 출력합니다.

 

Java Code

package com.java.algorithm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ_14502_연구소 {
	static int R,C;
	static int[][] map;
	static int[][] copyMap;
	static boolean[][] visited;
	static List<Virus> virusPos;
	
	static class Virus{
		int y,x;

		public Virus(int y, int x) {
			super();
			this.y = y;
			this.x = x;
		}
		
	}
	static int dy[] = {1,-1,0,0};
	static int dx[] = {0,0,-1,1};
	static int ans;
	static int virusCnt;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		
		map = new int[R][C];
		visited = new boolean[R][C];
		virusPos = new ArrayList<>();
		for (int i = 0; i < R; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < C; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if(map[i][j] == 2) {
					virusPos.add(new Virus(i, j));
				}
			}
		}
		ans = Integer.MIN_VALUE;
		setWalls(0);

		System.out.println(ans);
	}
	private static void setWalls(int cnt) {
		if(cnt == 3) {
			//바이러스 퍼뜨리기
			spread();
//			System.out.println("-------------------------");
//			for (int i = 0; i < R; i++) {
//				for (int j = 0; j < C; j++) {
//					System.out.print(map[i][j] +" ");
//				}
//				System.out.println();
//			}
			
			int total = 0;
			//바이러스가 최소로 퍼져야 안전영역이 최대
			//안전영역 개수 카운트
			for (int i = 0; i < R; i++) {
				for (int j = 0; j < C; j++) {
					if(copyMap[i][j] == 0) {
						total++;
					}
				}
			}
			
			ans = Math.max(ans, total);
			
			
			return;
		}
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				if(map[i][j]==0) {
					map[i][j] = 1;
					setWalls(cnt+1);
					map[i][j] = 0;
				}
			}
		}
		
	}
	private static int spread() {
		Queue<Integer[]> q = new LinkedList<>();
		copyMap = copyMap(map);
		boolean[][] spreadChecked = new boolean[R][C];
		for (int i = 0; i < virusPos.size(); i++) {
			int y = virusPos.get(i).y;
			int x = virusPos.get(i).x;
			Integer temp[] = {y,x};
			q.add(temp);
		}
		int total = 0;
		while(!q.isEmpty()) {
			int size = q.size();
			while(size-- > 0) {
				Integer[] pos = q.poll();
				for (int d = 0; d < 4; d++) {
					int ny = pos[0] + dy[d];
					int nx = pos[1] + dx[d];
					if(ny >= R || ny < 0 || nx >= C || nx < 0) continue;
					if(map[ny][nx] == 0 && !spreadChecked[ny][nx]) {
						spreadChecked[ny][nx] = true;
						copyMap[ny][nx] = 2; // 바이러스 표시
						Integer next[] = {ny,nx};
						q.add(next);
					}
				}
			}
		}
		return total;
	}
	private static int[][] copyMap(int[][] origin) {
		int[][] copy = new int[R][C];
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				copy[i][j] = origin[i][j];
			}
		}
		return copy;
		
	}

}