[백준 JAVA] 14502번: 연구소

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

 

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

public class Main {
	public static int n, m, max = 0, zero = 0, two = 0;
	public static int[][] map, emap, vmap;
	public static int[] dx = { 0, 0, 1, -1 };
	public static int[] dy = { 1, -1, 0, 0 };
	public static int[] arr = new int[3];

	public static class Dot {
		int x = 0;
		int y = 0;

		public Dot() {
			super();
		}

		public Dot(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}
	}
	
	public static void main(String[] args) throws IOException {
		// 1. 입력값 받아오기
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		// 1-1. n, m 입력값 받기
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		// map 범위 지정 map[n][m]
		map = new int[n][m];

		// 1-2. map 입력값 받기, 1의 수 2의 수 0의 수 세기 0의 좌표, 2의 좌표 저장
		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) {
					zero++;
				} else if (map[i][j] == 2) {
					two++;
				}
			}
		}
		emap = new int[zero][2];
		vmap = new int[two][2];
		int cnt = 0, cnt2 = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (map[i][j] == 0) {
					emap[cnt][0] = i;
					emap[cnt][1] = j;
					cnt++;
				} else if (map[i][j] == 2) {
					vmap[cnt2][0] = i;
					vmap[cnt2][1] = j;
					cnt2++;
				}
			}
		}
		// 2. 세울수 있는 벽 선정하기 0에 범위에서만 선택 => dfs
		dfs(0, 0);

		// 5. max 출력
		System.out.println(max);

	}

	public static void dfs(int at, int depth) {
		if (depth == 3) {
			// 2-1. 0을 1로 바꾸기
			for (int i = 0; i < 3; i++) {
				int cur = arr[i];
				int x = emap[cur][0];
				int y = emap[cur][1];
				map[x][y] = 1;
			}
			// 3. 바이러스가 퍼질 수 있는 범위 => bfs
			bfs();
			// 4-2. 1을 0으로 바꾸기 2~4 반복
			for (int i = 0; i < 3; i++) {
				int cur = arr[i];
				int x = emap[cur][0];
				int y = emap[cur][1];
				map[x][y] = 0;
			}
			return;
		}

		for (int i = at; i < zero; i++) {
			arr[depth] = i;
			dfs(i + 1, depth + 1);
		}
	}

	public static void bfs() {
		Queue<Dot> q = new LinkedList<>();
		for (int i = 0; i < two; i++) {
			int x = vmap[i][0];
			int y = vmap[i][1];
			Dot d = new Dot(x, y);
			q.offer(d);
		}
		
		int copyMap[][] = new int[n][m];
		for(int i = 0;i<n;i++) {
			copyMap[i] = map[i].clone();
		}

		while (!q.isEmpty()) {
			Dot cur = q.poll();
			int x = cur.x;
			int y = cur.y;
			for (int i = 0; i < 4; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
					if(copyMap[nx][ny] == 0) {
						q.offer(new Dot(nx, ny));
						copyMap[nx][ny] = 2;
					}
				}
			}
		}

		// 4. 안전 영역의 크기 구하기
		int size = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if(copyMap[i][j] == 0) {
					size++;
				}
			}
		}
		
		if(size > max) {
			max = size;
		}
		// 4-1. max와 비교한 뒤 더 크면 max 교체


	}

}

 

public static int n, m, max = 0, zero, one, two;
public static int[][] map;
public static int[] dx = {0, 0, 1, -1};
public static int[] dy = {1, -1, 0, 0};
public static int[2][] emap, vmap

// 1. 입력값 받아오기
// 1-1. n, m 입력값 받기
//        map 범위 지정 map[n][m]
// 1-2. map 입력값 받기, 1의 수 2의 수 0의 수 세기 0의 좌표, 2의 좌표 저장
// 2. 세울수 있는 벽 선정하기 0에 범위에서만 선택 => dfs 조합
// 2-1. 0을 1로 바꾸기
// 3. 바이러스가 퍼질 수 있는 범위 => bfs
// 3-1. 갯수를 센 뒤 안전영역 크기 구하기
// 4. 안전 영역의 크기 구하기
// 4-1. max와 비교한 뒤 더 크면 max 교체
// 4-2. 1을 0으로 바꾸기 2~4 반복
// 5. max 출력

 

풀이시간: 2시간

풀이방법: dfs, bfs