[BOJ/Java] 14502 : 연구소

 

문제

 

 

www.acmicpc.net/problem/14502

14502번: 연구소

 

 

 

풀이

 

 

• 벽 세개를 어떻게 채울 지 고민했던 문제. 이차원 배열에서 벽을 세울 모든 경우의 수만큼 .. 어떻게 해야 하나 싶었다. / 알고보니 평소 조합 함수를 세웠던 것과 매우! 비슷하게 cnt == 3 일 때의 기저조건을 세워주고 재귀함수를 구현하면 되는 거였다 !
• 이렇게 하지 않고도 벽을 세울 수 있는 부분을 큐?같은 자료구조에 넣어두고 조합함수를 돌려도 된다.

 

 

 

코드

 

 

import java.util.*;
import java.io.*;
import java.nio.Buffer;

public class Main {
	static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int[][] dir = { { -1, 0 }, { 1, 0 }, { 0, 1 }, { 0, -1 } };
	static int[][] map;
	static int[][] copyMap;
	static int N, M;
	static boolean[][] visited;
	static int answer = 0;

	public static void main(String[] args) throws Exception {
		st = new StringTokenizer(in.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		map = new int[N + 1][M + 1];
		for (int i = 1; i < N + 1; i++) {
			st = new StringTokenizer(in.readLine());
			for (int j = 1; j < M + 1; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		copyMap = new int[N + 1][M + 1]; //map자체를 수정하지 않기 위해 copy map을 만들어줌
		makeWall(0);
		System.out.println(answer);
	}

	private static void makeWall(int cnt) {//벽 3개를 세울 수 있는 모든 경우의 수만큼 계산하는 함수
		if (cnt == 3) { //벽 3개를 모두 만들었다면
			
			visited = new boolean[N + 1][M + 1];
			for (int i = 1; i < N + 1; i++) {
				for (int j = 1; j < M + 1; j++) {
					copyMap[i][j] = map[i][j]; //벽 3개를 만든 map을 copyMap에 복사
				}
			}
			
			for (int i = 1; i < N + 1; i++) {
				for (int j = 1; j < M + 1; j++) {
					if (copyMap[i][j] == 2 && !visited[i][j]) { //바이러스가 퍼짐(DFS)
						DFS(i, j);
					}
				}
			}
			//바이러스가 모두 퍼진 뒤, 안전영역의 개수(0)을 셈
			int safeAreaCount = countZero();

			if (answer < safeAreaCount) {
				answer = safeAreaCount;
			}
			return;
		}
		for (int i = 1; i < N + 1; i++) {
			for (int j = 1; j < M + 1; j++) {
				if (map[i][j] == 0) {
					
					map[i][j] = 3;
					makeWall(cnt + 1);
					map[i][j] = 0;		
					
				}
			
			}
		}
	}

	private static void DFS(int x, int y) {

		visited[x][y] = true;

		for (int d = 0; d < 4; d++) {
			int dx = x + dir[d][0];
			int dy = y + dir[d][1];
			if (dx < 1 || dy < 1 || dx > N || dy > M)
				continue;
			if (visited[dx][dy])
				continue;
			if (copyMap[dx][dy] == 0) {
				copyMap[dx][dy] = 2;
				DFS(dx, dy);
			}
		}

	}

	private static int countZero() {
		int count = 0;
		for (int i = 1; i < N + 1; i++) {
			for (int j = 1; j < M + 1; j++) {
				if (copyMap[i][j] == 0) {
					count++;
				}
			}
		}
		return count;
	}
}