[백준] 14502: 연구소 문제 풀이

현톨·2023년 2월 22일
0

Algorithm

목록 보기
39/42

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

조합

벽 3개를 놓을 수 있는 모든 경우의 수를 구해야 한다.
N*M 크기의 배열의 각 칸을 0~N*M-1까지의 번호로 가정을 하고, 해당 범위 중 3개를 고를 수 있는 조합을 만든다.

조합으로 만들어진 3개의 수 각각 i에서
i/M 은 y축, i%M은 x축으로 본다.
(i/M, i%M) 위치에 바이러스가 있으면 해당 수는 조합에 포함하지 않는다.

static void comb(int cnt, int idx) {
	if (cnt == 3) {
		// 다음 단계로 진행
		return;
	}
	for (int i=idx; i<N*M; i++) {
		if (arr[i/M][i%M]!=0) continue; // 해당 위치에 바이러스가 있으면 조합에 포함 x
		comb[cnt] = i;
		comb(cnt+1, i+1);
	}
}

바이러스 확산

벽을 놓을 조합이 완성되면, 기존 배열을 복제한 후에, 각 세 위치에 벽을 놓고, 바이러스를 확산시킨다.
확산 시킨 후에 배열을 검사하여 빈 공간의 갯수만큼 세어준 후에 최댓값을 갱신한다.

static void dfs() {
	ArrayDeque<int []> q = new ArrayDeque<>();
	for (int [] v : virus) q.add(v);
	while (!q.isEmpty()) {
		int [] v = q.poll();
		int y = v[0], x = v[1];
		newArr[y][x] = 2;
		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (0<=ny&&ny<N&&0<=nx&&nx<M&&newArr[ny][nx]==0)
				q.add(new int[] {ny,nx});
		}
	}
}
	
static void comb(int cnt, int idx) {
	if (cnt == 3) {
		for (int i=0; i<N; i++) newArr[i]=Arrays.copyOf(arr[i], M); // 배열 복제
		for(int i : comb) newArr[i/M][i%M] = 1; // 각 위치에 벽 놓기
		dfs(); // 바이러스 확산
		int area = count(); // 빈 공간의 갯수 카운트
		ans = area>ans?area:ans; // 최댓값 갱신
		return;
	}
	for (int i=idx; i<N*M; i++) {
		if (arr[i/M][i%M]!=0) continue;
		comb[cnt] = i;
		comb(cnt+1, i+1);
	}
}

전체 코드

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

# public class Main {
	static int N, M, ans = 0;
	static int [][] arr, newArr;
	static int [] comb = new int [3];
	static int [] dy = {-1, 1, 0, 0};
	static int [] dx = {0, 0, -1, 1};
	static List <int[]> virus = new ArrayList<>();
	
	static int count() {
		int sum = 0;
		for (int i = 0; i < N; i++) 
			for (int j = 0; j < M; j++)
				if (newArr[i][j]==0)sum++;
		return sum;
	}
	
	static void dfs() {
		ArrayDeque<int []> q = new ArrayDeque<>();
		for (int [] v : virus) q.add(v);
		while (!q.isEmpty()) {
			int [] v = q.poll();
			int y = v[0], x = v[1];
			newArr[y][x] = 2;
			for (int i = 0; i < 4; i++) {
				int ny = y + dy[i];
				int nx = x + dx[i];
				if (0<=ny&&ny<N&&0<=nx&&nx<M&&newArr[ny][nx]==0)
					q.add(new int[] {ny,nx});
			}
		}
	}
	
	static void comb(int cnt, int idx) {
		if (cnt == 3) {
			for (int i=0; i<N; i++) newArr[i]=Arrays.copyOf(arr[i], M);
			for(int i : comb) newArr[i/M][i%M] = 1;
			dfs();
			int area = count();
			ans = area>ans?area:ans;
			return;
		}
		for (int i=idx; i<N*M; i++) {
			if (arr[i/M][i%M]!=0) continue;
			comb[cnt] = i;
			comb(cnt+1, i+1);
		}
	}
	
	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());
		arr = new int [N][M];
		newArr = new int[N][M];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < M; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
				if (arr[i][j] == 2) virus.add(new int[] {i, j});
			}
		}
		comb(0, 0);
		br.close();
		System.out.println(ans);
	}
}
profile
기록하는 습관 들이기

0개의 댓글