BOJ - 14502 연구소

14502 연구소 : https://www.acmicpc.net/problem/14502

Problems

---

Solves

벽을 세우는 일과 바이러스를 퍼트리는 일을 분리해서 생각을 했다.
벽을 세우는 일은 백트래킹을 사용하여 3개의 벽을 세우고(dfs) 3개의 벽을 세웠을 때 바이러스를 퍼트리는 함수를 호출(bfs)하였다.
바이러스를 퍼트리는 함수에서는 바이러스의 갯수를 count하여 그 갯수를 반환하여 바이러스의 갯수가 작을수록 안전지역이 커지므로 Math.min의 값을 갱신하였다.
안전지역 = N*M - (벽 갯수 + 임의로 세운 벽 갯수(3) + 바이러스 갯수)를 계산하여 반환.

---

Code

public class 연구소 {
	static int[][] map;
	static int N;
	static int M;
	static int virusCount;
	static int wallCount;
	static List<Point> virusList;

	static int[] dy = {-1, 0, 1, 0};
	static int[] dx = {0, -1, 0, 1};

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		map = new int[N][M];
        //바이러스 좌표 저장 리스트
		virusList = new ArrayList<>();
        //바이러스 갯수 최대치로 초기화
		virusCount = N*M;
        //벽 갯수
		wallCount = 0;
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < M; j++) {
				int e = Integer.parseInt(st.nextToken());
				map[i][j] = e;
                //바이러스일 때 바이러스 좌표 저장
				if (e == 2) {
					virusList.add(new Point(j, i));
				}
                //벽일 때 벽 갯수 갱신
				if (e == 1)
					wallCount++;
			}
		}

		//벽 세우기
		setWall(0, 0);
        
        //최소값의 virusCount를 통해 안전구역 크기 반환
		int res = (N * M) - (wallCount + 3 + virusCount);
		bw.write(String.valueOf(res));
		bw.flush();
		bw.close();
	}

	//벽세우기 dfs
    //count : 벽 갯수, x : map의 x좌표(x좌표를 통해 x좌표 이전의 좌표는 탐색할 필요가 없어 시간 절약)
	static void setWall(int count, int x) {
    	//벽 갯수가 3이 되면 바이러스를 뿌리는 함수(spreadVirus)호출 및 최소 바이러스 갯수 갱신
		if (count >= 3) {
			virusCount = Math.min(virusCount, spreadVirus());
			return;
		}

		/*
        map을 탐색하면서 x좌표 이상부터 map[j][i]의 값이 2(바이러스)와 1(벽)이 아닌 곳을 탐색하며 벽을 세우고 백트래킹
        */
		for (int i = x; i < M; i++) {
			for (int j = 0; j < N; j++) {
				if (map[j][i] == 2 || map[j][i] == 1)
					continue;
				map[j][i] = 1;
				setWall(count + 1, i);
				map[j][i] = 0;
			}
		}
	}

	//바이러스 뿌리기 bfs
    /*
    저장한 바이러스 리스트의 크기를 최소 바이러스 갯수로 두고 바이러스가 빈 공간의 방문 여부를 확인하는 visit 2중 배열을 초기화 한 후 상하좌우의 좌표를 탐색하여 빈 공간에만 접근 할수 있도록 하여 바이러스 갯수를 카운트한다.
    */
	static int spreadVirus() {
		Queue<Point> queue = new LinkedList<>();
		boolean[][] visit = new boolean[N][M];
		for (Point point : virusList) {
			queue.offer(point);
			visit[point.y][point.x] = true;
		}
		int count = virusList.size();
		while (!queue.isEmpty()) {
			Point p = queue.poll();

			for (int i = 0; i < 4; i++) {
				int ny = p.y + dy[i];
				int nx = p.x + dx[i];
                //map범위 초과 || 벽 || 존재하는 바이러스는 무시한다.
				if (ny < 0 || nx < 0 || ny >= N || nx >= M || map[ny][nx] == 1 || visit[ny][nx])
					continue;
				visit[ny][nx] = true;
				count++;
				queue.offer(new Point(nx, ny));
			}
		}
        //map에 퍼진 바이러스의 갯수 반환
		return count;
	}

	static class Point {
		int x;
		int y;

		public Point(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
}

---

Result