백준_연구소_14502

// 알고리즘

1. bfs

 

2. 3개의 벽을 세움

 -> v[N][M][N][M][N][M] 방문배열을 사용하여 중복계산제거

 

3. 벽을 세운 후 바이러스 퍼뜨리기

 -> 기존의 map을 입력할 때 바이러스 위치를 dq에 저장해놓고 bfs 시작 시 dq에 있는 모든값을 q에 집어넣고 시작

 -> 4방 탐색 

 -> 바이러스가 증식한 개수를 카운팅

 

4. 결과

 -> 기존의 맵을 입력받을 때 0의 개수 카운팅

 -> 0의 개수 -  증식한 개수 - 3(벽) 

 -> 최대값 

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

public class 연구소_14502 {

	static int N, M, ans,cnt_zero;
	static boolean v[][][][][][];
	static Queue<Point> dq;
	static Queue<Point> q = new LinkedList<>();
	static int[] dr = { -1, 1, 0, 0 };
	static int[] dc = { 0, 0, -1, 1 };

	static class Point {
		int r, c;

		public Point(int r, int c) {
			this.r = r;
			this.c = c;
		}

	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		int[][] map = new int[N][M];
		v = new boolean[N][M][N][M][N][M];
		dq = new LinkedList<>();
		ans = 0;

		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] == 2)
					dq.add(new Point(i, j));
				if(map[i][j] == 0) {
					cnt_zero++;
				}
			}
		}

		cal(0, new int[6], map);
		System.out.println(ans);
//		print(map);

	}

	private static void cal(int idx, int[] vv, int[][] map) {
		if (idx == 6) {
			if (v[vv[0]][vv[1]][vv[2]][vv[3]][vv[4]][vv[5]] || v[vv[0]][vv[1]][vv[4]][vv[5]][vv[2]][vv[3]]
					|| v[vv[2]][vv[3]][vv[0]][vv[1]][vv[4]][vv[5]] || v[vv[4]][vv[5]][vv[0]][vv[1]][vv[2]][vv[3]]
					|| v[vv[2]][vv[3]][vv[4]][vv[5]][vv[0]][vv[1]] || v[vv[4]][vv[5]][vv[2]][vv[3]][vv[0]][vv[1]])
				return;

			v[vv[0]][vv[1]][vv[2]][vv[3]][vv[4]][vv[5]] = true;

			// 알고리즘
			bfs(map, new boolean[N][M]);

			return;
		}

		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map[i].length; j++) {
				if (map[i][j] == 0) {
					map[i][j] = 1;
					vv[idx] = i;
					vv[idx + 1] = j;
					cal(idx + 2, vv, map);
					map[i][j] = 0;
					vv[idx] = 0;
					vv[idx + 1] = 0;
				}
			}
		}

	}

	private static void bfs(int[][] map, boolean[][] vvv) {
		q.clear();
		q.addAll(dq);
		
		Point p = null;
		int cnt = 0;
		while(!q.isEmpty()) {
			p = q.poll();
			vvv[p.r][p.c] = true;
			
			for (int k = 0; k < 4; k++) {
				int nr = p.r +  dr[k];
				int nc = p.c +  dc[k];
				
				if(nr < 0 || nc < 0 || nr >= N || nc >= M || vvv[nr][nc]) continue;
				if(map[nr][nc] == 1 || map[nr][nc] == 2) continue;
				vvv[nr][nc] = true;
				cnt ++;
				q.add(new Point(nr,nc));
				
			}
			
		}
		
		ans = Math.max(ans,cnt_zero - cnt-3);
		
		

	}


	private static void print(int[][] map) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				System.out.print(map[i][j] + " ");
			}
			System.out.println();
		}

	}

}

 

※ N과 M 의 최대값이 8이고 최악의 경우라도 8C3 이기 때문에 완탐이 가능하다고 판단함.

  중복을 제거하기 위해 6차원 방문 배열을 사용했는데 중복을 생각안하고 8*7*6 을 해도 14만정도라 풀릴거같음.

  중복제거하는 방법이 지저분해서 다른 좋은방법을 찾아봐야겠음.