[백준/Java] 14502 연구소

14502

접근법

풀이 자체는 치킨배달과 비슷한데 2차원 배열 깊은 복사가 안 돼서 오래 애먹은 문제...
치킨배달 문제와 마찬가지로 효율적으로 벽 세울 고민보다는 가능한 조합 전부 해봐야 하는 완전탐색 문제다.

1. 2차원 배열로 map 입력을 받고 벽을 세울 수 있는 공간의 좌표와 바이러스의 위치 좌표도 각각 list에 저장해준다.
2. makeWall = 조합 만드는 코드와 비슷한데, 세울 수 있는 모든 벽을 세워준다.
3. 벽을 세울 위치 세군데를 정하면 (=조합 하나를 완성하면)
   • 새 지도를 만들어서 벽을 세워주고 (그래야 다음에 새로운 벽을 세울 때 이전에 퍼진 바이러스의 영향 없이 바이러스를 퍼뜨릴 수 있다)
   • 지도를 전부 돌면서 바이러스를 퍼뜨린다 = bfs
   • 바이러스가 모두 퍼진 지도에서 안전한 곳(0인 곳) 의 개수를 cnts 배열에 저장한다
4. cnts 배열에서 가장 큰 수를 출력한다.

코드

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

public class BOJ14502 {
	static int N;
	static int M;
	static int[][] map;
	static int cnt = 0;
	static ArrayList<Position> blank = new ArrayList<>();
	static ArrayList<Position> virus = new ArrayList<>();
	static Position walls[] = new Position[3];
	static ArrayList<Integer> cnts = new ArrayList<>();
	
	static int[] dx = { 1, -1, 0, 0};
	static int[] dy = { 0, 0, 1, -1};
	
	static class Position {
		int x;
		int y;
		
		Position(int x, int y){
			this.x = x;
			this.y = y;
		}

		@Override
		public String toString() {
			return "Position [x=" + x + ", y=" + y + "]";
		}
		
		
	}
	
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		map = new int[N][M];
		
		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) {
					blank.add(new Position(j,i));
				}
				else if (map[i][j] == 2) {
					virus.add(new Position(j,i));
				}
			}
		}
		
		makeWall(0, 0);
		cnts.sort(null);
		System.out.println(cnts.get(cnts.size()-1));
		
	}

	
	static void makeWall(int idx, int targetIdx) {
		if (targetIdx == 3) {
			int [][] newMap = new int[N][M];
			for(int i=0; i<N; i++) {
				for(int j=0; j<M; j++)  {
					newMap[i][j] = map[i][j];
				}
			}
			newMap[walls[0].y][walls[0].x] = 1;
			newMap[walls[1].y][walls[1].x] = 1;
			newMap[walls[2].y][walls[2].x] = 1;
			
			
			boolean[][] visited = new boolean[N][M];
			cnt = 0;
			for (int i = 0; i < virus.size(); i++) {
				Position vir = virus.get(i);
				if (!visited[vir.y][vir.x]) {
					bfs(virus.get(i).x, virus.get(i).y, newMap, visited);	
				}
			}
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M;j++) {
					if (newMap[i][j] == 0) cnt++;
				}
			}
			cnts.add(cnt);
			newMap[walls[0].y][walls[0].x] = 0;
			newMap[walls[1].y][walls[1].x] = 0;
			newMap[walls[2].y][walls[2].x] = 0;

			return;
		}

		for (int i = idx; i < blank.size(); i++) {
			walls[targetIdx] = blank.get(i);
			makeWall(i+1, targetIdx+1);
		}
	}
	
	static void bfs(int x, int y, int[][] map2, boolean[][] visited) {
		Queue<Position> queue = new LinkedList<>();
		queue.offer(new Position(x,y));
		visited[y][x] = true;
		int nx = 0;
		int ny = 0;
		
		while(!queue.isEmpty()) {
			
			Position temp = queue.poll();
			
			for (int d = 0; d < 4; d++) {
				nx = temp.x + dx[d];
				ny = temp.y + dy[d];
				
				if (nx >= 0 && ny >= 0 && nx < M && ny < N) {
					if (map2[ny][nx] == 0) {
						map2[ny][nx] = 2;
						queue.add(new Position(nx,ny));
						visited[ny][nx] = true;
					}
				}
			}
		}
	}
}