[백준 14502번] 연구소

www.acmicpc.net/problem/14502

14502번: 연구소

문제 풀이

 

입력이 작기 때문에 벽 생성이 가능한 모든 경우에 벽을 세운 뒤, 바이러스를 퍼트려 최대 공간을 찾아내면 됩니다.

 

---

 

구현 상의 팁이라면 이차원 배열의 상의 가능한 세가지 조합을 구할 때, 요소들의 번호를 1차원화시키는게 편합니다.

 

4x3 행렬이라면

 

0 1 2

3 4 5

6 7 8

9 10 11   

 

위와 같이 번호를 매기면 단순하게 3중 for문을 이용해 모든 경우를 찾을 수 있습니다.

그리고 좌표 평면으로 변환도 쉽습니다.

임의의 번호 a를 골랐다면 a에 대응하는 2차원 좌표는 (a/m, a%m)이 됩니다.

(m은 2차원 배열의 가로 길이 입니다. 위의 예에서는 3이 되겠네요)

 

 

 

package backjoon.graph.p14502;

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

public class Main {
	static int n,m, wallCnt=0;
	static int[][] map;
	static boolean[][] discovered;
	static List<Point> virusList;
	public static void main(String[ ] args) throws IOException {
//		InputReader reader = new InputReader("testcase.txt");
		InputReader reader = new InputReader();
		StringTokenizer st = new StringTokenizer(reader.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		map = new int[n][m];
		virusList = new ArrayList<>();
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(reader.readLine());
			for (int j = 0; j < m; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if(map[i][j] == 2) virusList.add(new Point(i,j));
				if(map[i][j] == 1) wallCnt++;
			}
		}

//		System.out.println(virusList);

		int ret = solve();
		System.out.println(ret);
	}

	private static int solve() {
		int max = 0;
		for (int i = 0; i < n*m; i++) {
			for (int j = i+1; j < n*m; j++) {
				for (int k = j+1; k < n*m; k++) {
					Point wall1 = new Point(i/m, i%m);
					Point wall2 = new Point(j/m, j%m);
					Point wall3 = new Point(k/m, k%m);

					if(isEmptySpace(wall1, wall2, wall3)) {
						discovered = new boolean[n][m];
						max = Math.max(max, infect(wall1, wall2, wall3));
					}
				}
			}
		}
		return max;
	}

	private static boolean isEmptySpace(Point wall1, Point wall2, Point wall3) {
		if(map[wall1.row][wall1.col] == 0 && map[wall2.row][wall2.col] == 0
				&& map[wall3.row][wall3.col] == 0) return true;
		return false;
	}

	static int[] dr = {1,-1,0,0};
	static int[] dc = {0,0,1,-1};

	private static int infect(Point wall1, Point wall2, Point wall3) {
		//벽 생성
		map[wall1.row][wall1.col] = 1;
		map[wall2.row][wall2.col] = 1;
		map[wall3.row][wall3.col] = 1;
		
		//큐 초기화 - 바이러스; 블록 큐에 저장
		Queue<Point> queue = new ArrayDeque<>();
		virusList.stream().forEach(p -> {
			discovered[p.row][p.col] = true;
			queue.add(p);
		});
		int totalInfected = virusList.size();

		while(!queue.isEmpty()) {
			Point here = queue.poll();

			for (int i = 0; i < 4; i++) {
				int nextR = here.row + dr[i];
				int nextC = here.col + dc[i];

				if(isRange(nextR, nextC) && map[nextR][nextC] == 0
						&&!discovered[nextR][nextC]) {
					totalInfected++;
					discovered[nextR][nextC] = true;
					queue.add(new Point(nextR, nextC));
				}
			}
		}

		//벽 제거 - 원상복구
		map[wall1.row][wall1.col] = 0;
		map[wall2.row][wall2.col] = 0;
		map[wall3.row][wall3.col] = 0;

		return n*m - totalInfected - (wallCnt+3);
	}

	private static boolean isRange(int nextR, int nextC) {
		if(nextR >= n || nextR < 0 || nextC >= m || nextC < 0) return false;
		return true;
	}

}
class Point {
	int row, col;
	public Point(int row, int col) {
		this.row = row;
		this.col = col;
	}

	@Override
	public String toString() {
		return "{row=" + row +
				", col=" + col +
				'}';
	}
}

class InputReader {
	private BufferedReader br;

	public InputReader() {
		br = new BufferedReader(new InputStreamReader(System.in));
	}

	public InputReader(String filepath) {
		try {
			br = new BufferedReader(new FileReader(filepath));
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}
	}

	public String readLine() throws IOException {
		return br.readLine();
	}
	public int readInt() throws IOException {
		return Integer.parseInt(readLine());
	}
}