[골드4] 14502. 연구소 (Java)

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

14502번: 연구소

Thanks to Judy~

---

※  문제를 요약하면 아래와 같습니다.

▶ NxM 맵 안에 벽과 바이이러스가 있는 곳이 주어지며, 바이러스는 상하좌우 인접한 벽이 아닌 곳으로 모두 퍼져나감

▶ 벽을 임의로 3곳에 세웠을 때, 안전한 장소가 가장 많은 갯수 출력

▶ Input : 첫째 줄에 공백을 구분으로 세로 N, 가로 M이 주어지며, 이후 N개의 줄에 맵의 상태주어짐

                (0 == 빈 칸, 1은 벽, 2는 바이러스)

▶ Output : 얻을 수 있는 안전 영역의 최대 크기 출력

---

◈ Input - 1

7 7
2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

◈ Output - 1

27

◈ Input - 2

4 6
0 0 0 0 0 0
1 0 0 0 0 2
1 1 1 0 0 2
0 0 0 0 0 2

◈ Output - 2

9

◈ Input - 3

8 8
2 0 0 0 0 0 0 2
2 0 0 0 0 0 0 2
2 0 0 0 0 0 0 2
2 0 0 0 0 0 0 2
2 0 0 0 0 0 0 2
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

◈ Output - 3

3

---

 ◎  코드 작성 전, 아래와 같이 솔루션을 정리하였습니다.

▶ (Row, Col) 포인트를 표현하기 위해 Point 클래스를 작성

▶ 값이 0인 곳의 포인트를 ArrayList에 Point 형태로 저장 

▶ 조합을 통해 0~ArrayList 크기-1 까지 세 곳의 인덱스를 뽑아 벽을 세운 후 BFS 적용

▶ BFS 는 델타 탐색으로 값이 0(SAFE)인 곳만 2로 변경

▶ BFS 하기 전 map의 값을 남겨 놓기 위해 새로운 2차운 배열 Temp를 시뮬레이션 용 배열로 선언

▶ BFS 종료후 벽을 임의로 세운 3곳을 다시 빈 칸으로 변경 후, Temp의 배열 값이 0인 곳을 카운트하여 Max값과 비교

▶ 모든 조합의 경우의 수 에서 0인 곳이 가장 많을 때, 최댓값 출력

---

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class Point {
	int m_nRow;
	int m_nCol;
	public Point(int m_nRow, int m_nCol) {
		super();
		this.m_nRow = m_nRow;
		this.m_nCol = m_nCol;
	}
}

public class Main {

	static int N, M, nMax;
	static int[][] narrMap, narrTemp;
	static ArrayList<Point> SafePoints, VirusPoints;
	
	static int[] narrWall = new int[3];
	static boolean[] barrWall;
	// 동, 서, 남, 북
	static int[] dr = {0,0,-1,1};
	static int[] dc = {1,-1,0,0};
	
	static final int SAFE = 0;
	static final int WALL = 1;
	static final int VIRUS = 2;
	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader bReader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bWriter = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(bReader.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		narrMap = new int[N][M];
		narrTemp = new int[N][M];
		SafePoints = new ArrayList<>();
		VirusPoints = new ArrayList<>();
		
		// zero 포인트들을 저장해놓자
		for(int i = 0 ; i < N; i++) {
			st = new StringTokenizer(bReader.readLine());
			for(int j = 0; j < M; j++) {
				narrMap[i][j] = Integer.parseInt(st.nextToken());
				if(narrMap[i][j] == SAFE)
					SafePoints.add(new Point(i,j));
				else if(narrMap[i][j] == VIRUS)
					VirusPoints.add(new Point(i, j));
			}
		}
		// 조합으로 구하자
		barrWall = new boolean[SafePoints.size()];
		// 0인 곳에 벽을 놓는 모든 경우의 수를 구하자
		GetPerm(0);

		bWriter.write(String.valueOf(nMax));
		bWriter.close();
	}
	private static void GetPerm(int nIndex) {
		// 기저 조건
		if(nIndex == 3) {
			// 벽을 세울 세칸의 포인트를 지정하였따
			// 템플릿에 복사해주자
			for(int i = 0; i < 3; i++)
				narrMap[SafePoints.get(narrWall[i]).m_nRow][SafePoints.get(narrWall[i]).m_nCol] = WALL;
			Copy();
			BFS();
			// 벽을 다시 없애주자
			for(int i = 0; i < 3; i++)
				narrMap[SafePoints.get(narrWall[i]).m_nRow][SafePoints.get(narrWall[i]).m_nCol] = SAFE;
			
			return;
		}
		
		// 재귀 조건
		
		for(int i = 0; i < SafePoints.size(); i++) {
			if(!barrWall[i]) {
				if(nIndex > 0 && narrWall[nIndex-1] > i) {
					continue;
				}
				barrWall[i] = true;
				narrWall[nIndex] = i;
				GetPerm(nIndex+1);
				barrWall[i] = false;
			}
		}
		
	}
	
	// 바이러스 퍼지는 과정을 BFS로 
	private static void BFS() {
		// 바이러스를 퍼트리자
		Queue<Point> queueBFS = new LinkedList<>();
		for(int i = 0; i < VirusPoints.size(); i++)
			queueBFS.add(VirusPoints.get(i));
		while(!queueBFS.isEmpty()) { 
			Point pTemp = queueBFS.poll();
			
			for(int i = 0; i < dr.length; i++) {
				int nSearchRow = pTemp.m_nRow + dr[i];
				int nSearchCol = pTemp.m_nCol + dc[i];
				
				// 범위 밖은 빠이
				if(nSearchRow < 0 || nSearchCol < 0 || nSearchRow >= N || nSearchCol >= M)
					continue;
				// 벽도 아니고 이미 바이러스도 아니면 퍼트려버려
				if(narrTemp[nSearchRow][nSearchCol] == SAFE) {
					narrTemp[nSearchRow][nSearchCol] = VIRUS;
					queueBFS.add(new Point(nSearchRow, nSearchCol));
				}
			}
		}

		// 바이러스 확산 끝나구
		// Max 값 비교하자
		getMaxSafe();
	}
	
	// Map의 값이 바뀌어버리면 돌이킬 수 없으니
	// 템플릿을 하나 만들어줘서 벽을 임의로 세우고 바이러스를 퍼트려보자
	private static void Copy() {	
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				narrTemp[i][j] = narrMap[i][j];
			}
		}
	}
	
	// 바이러스가 전부 퍼진뒤
	// 안전한 공간을 카운트 해서 최댓값과 비교하자
	private static void getMaxSafe() {
		int nCount = 0;
		// 0인값 == 안전 공간
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				if(narrTemp[i][j] == SAFE)
					nCount++;
			}
		}
		
		if(nMax < nCount)
			nMax = nCount;
	}

}

---

Good Luck! (피드백 감사합니다!)