문제
구현 방법
벽 3개를 세울 수 있는 모든 경우의 수를 구해야합니다.
미리 빈칸의 개수와 좌표를 저장해두어 빈칸 중 3개를 구하여 구할 때마다 dfs를 돌려 바이러스를 퍼트려줍니다.
바이러스가 적게 퍼져야 안전영역이 커지므로 바이러스가 퍼지는 개수를 구해주어 이들의 최솟값을 구하여 안전영역의 최댓값을 구해줍니다.
구현 코드
package BOJ.Gold;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class BOJ14502_연구소 {
static int R, C, MIN, danger;
static int[] select;
static int[][] lab, deltas = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
static boolean[][] visited;
static List<Move> blank, virus;
static class Move {
int r, c;
public Move(int r, int c) {
super();
this.r = r;
this.c = c;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
lab = new int[R][C];
blank = new ArrayList<>();
virus = new ArrayList<>();
int blankCnt = 0;
for (int r=0;r<R;r++) {
st = new StringTokenizer(br.readLine());
for (int c=0;c<C;c++) {
lab[r][c] = Integer.parseInt(st.nextToken());
if (lab[r][c]==2) virus.add(new Move(r, c)); // 바이러스 저장
else if (lab[r][c]==0) { // 빈칸일 때
blankCnt++; // 빈칸 개수 세어주기
blank.add(new Move(r, c)); // 빈칸 저장
}
}
}
// 입력완료
select = new int[3];
MIN = Integer.MAX_VALUE;
combination(0, 0); // 조합 구하기
int labSize = blankCnt-3-MIN+virus.size(); // 빈칸의 개수 - 벽 3개 - 바이러스 퍼진 구간 + 중복된 바이러스 개수
System.out.println(labSize);
}
static void combination(int cnt, int start) {
if (cnt==3) { // 3개 고르면
visited = new boolean[R][C];
for (int i=0;i<3;i++) {
int r = blank.get(select[i]).r;
int c = blank.get(select[i]).c;
visited[r][c] = true; // 선택된 빈칸 3개 좌표 방문처리
}
danger = 0;
for (int r=0;r<R;r++) {
for (int c=0;c<C;c++) {
if (!visited[r][c] && lab[r][c] == 2) { // 바이러스 퍼져라!!
dfs(r, c);
}
}
}
MIN = Math.min(MIN, danger); // 최솟값 구하기 (바이러스가 제일 적게 퍼져야 안전영역이 커짐)
return;
}
for (int i=start;i<blank.size();i++) { // 크기가 3 조합구하기
select[cnt] = i;
combination(cnt+1, start+1);
}
}
static void dfs(int r, int c) {
if (MIN<danger) return; // 최솟값보다 커지면 그만 구하기
danger++;
for (int d=0;d<4;d++) {
int nr = r+deltas[d][0];
int nc = c+deltas[d][1];
if (isIn(nr, nc) && !visited[nr][nc] && lab[nr][nc] ==0) {
visited[nr][nc] = true;
dfs(nr, nc);
}
}
return;
}
static boolean isIn(int nr, int nc) {
return nr>=0 && nr<R && nc>=0 && nc<C;
}
}
'백준' 카테고리의 다른 글
백준 2146번 : 다리 만들기 (0) | 2021.04.09 |
---|---|
백준 17472번 : 다리 만들기2 (0) | 2021.04.05 |
백준 1600번 : 말이 되고픈 원숭이 (0) | 2021.04.05 |
백준 9205번 : 맥주 마시면서 걸어가기 (0) | 2021.04.05 |
백준 19236번 : 청소년 상어 (0) | 2021.04.05 |