백준 14502번: 연구소
풀이
- DFS로 3개의 벽을 선택
- 3개의 벽이 선택되면 BFS로 바이러스를 퍼트리고 안전공간의 크기를 구한다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
//벽은 꼭 3개를 세워야 한다.
public class Problem14502 {
static int weight, height = -1;
static int[] dirX = new int[]{0,0,1,-1};
static int[] dirY = new int[]{1,-1,0,0};
static int[][] map;
static boolean[][] visited;
static int answerMax = 0;
//바이러스를 퍼트린 뒤 안전공간 수 반환
public static int bfs(){
//map의 복사
int[][]mapDup = new int[map.length][map[0].length];
for(int i=0; i<map.length; i++){
System.arraycopy(map[i], 0, mapDup[i], 0, map[0].length);
}
visited = new boolean[mapDup.length][mapDup[0].length];
Queue<int[]> queue = new LinkedList<>();
int answer = 0;
for(int i = 0; i < mapDup.length; i++){
for(int j = 0; j < mapDup[0].length; j++){
if(mapDup[i][j]==2){
queue.add(new int[]{i, j});
visited[i][j] = true;
}
}
}
while(!queue.isEmpty()) {
int[] currNode = queue.poll();
for (int d = 0; d < 4; d++) {
int newX = currNode[1] + dirX[d];
int newY = currNode[0] + dirY[d];
if (newX < 0 || newX >= weight || newY < 0 || newY >= height) continue;
//4방향에 값이 존재 & 미방문
if (mapDup[newY][newX] == 0 && !visited[newY][newX]) {
queue.add(new int[]{newY, newX});
mapDup[newY][newX] = 2;
visited[newY][newX] = true;
}
}
}
for(int i = 0; i < mapDup.length; i++) {
for (int j = 0; j < mapDup[0].length; j++) {
if (mapDup[i][j] == 0) {
answer++;
}
}
}
return answer;
}
public static void dfs(int wallNum){
//벽 3개 설치. bfs로 안전공간 최대치 구함
if(wallNum==3){
int answerTemp = bfs();
if(answerTemp > answerMax){
answerMax = answerTemp;
}
} else {
for(int i = 0; i < map.length; i++) {
for (int j = 0; j < map[0].length; j++) {
if(map[i][j]==0){
map[i][j] = 1;
dfs(wallNum+1);
map[i][j] = 0;
}
}
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String s = br.readLine();
StringTokenizer st = new StringTokenizer(s, " ");
height = Integer.parseInt(st.nextToken());
weight = Integer.parseInt(st.nextToken());
map = new int[height][weight];
for(int i = 0; i < height; i++){
String nodeStr = br.readLine();
StringTokenizer nodeSt = new StringTokenizer(nodeStr, " ");
for(int j = 0; j < weight; j++){
map[i][j] = Integer.parseInt(nodeSt.nextToken());
}
}
for(int i = 0; i < map.length; i++) {
for (int j = 0; j < map[0].length; j++) {
if(map[i][j]==0){
map[i][j] = 1;
dfs(1);
map[i][j] = 0;
}
}
}
System.out.println(answerMax);
}
}
Author And Source
이 문제에 관하여(백준 14502번: 연구소), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@haribo/백준-14502번-연구소저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)