[백준] 14502 연구소 - 브루트포스(BruteForce) + BFS(너비우선탐색) + 조합(Combination) JAVA

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

14502번: 연구소

코드설명

브루트포스(BruteForce) + BFS(너비우선탐색) + 조합(Combination) 문제입니다.

 

벽을 3개 세우는 조합을 통해 벽을 세우고 바이러스를 퍼뜨린뒤 안전 영역의 최대값을 계산합니다.

코드로직입니다.

1. simulate 메서드: 벽을 세우는 경우의 수를 확인하는 메서드입니다. 재귀적으로 호출되며, 현재 위치의 칸에 벽을 세우거나 세우지 않는 모든 경우를 탐색합니다. 벽을 세울 때마다 BFS를 통해 바이러스의 퍼짐을 시뮬레이션하고, 안전 지역의 개수를 계산합니다.
2. BFS 메서드: 바이러스의 퍼짐을 BFS로 시뮬레이션합니다. 바이러스가 퍼진 지역의 개수를 세고, 이를 최소값으로 갱신합니다.
3. Node 클래스: 좌표를 나타내는 클래스로, 바이러스의 위치를 저장하기 위해 사용됩니다.

문제에서 최대 안전지대 = (N*M) - (바이러스가 최소 퍼질 수 있는 개수) - (안전증검다리 개수) 를 사용하여 답을 구했습니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	public static int N,M, K;
	public static int[][] map;
	public static int answer = 8 * 8 + 1;
	public static int wallCnt = 3;
	public static Queue<Node> virusQ = new LinkedList<>();
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());

    	N = Integer.parseInt(st.nextToken());
    	M = Integer.parseInt(st.nextToken());
    	map = new int[N][M];
    	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) {
    				virusQ.offer(new Node(i, j));
    			}
    			if(map[i][j] == 1) {
    				wallCnt += 1;
    			}
    		}
    	}
    	
    	simulate(0, 0, 0, 0);
    	//최대 안전지대 = (N*M) - (바이러스가 최소 퍼질 수 있는 개수) - (안전증검다리 개수)
    	System.out.println(N*M - wallCnt - answer);
    }
    

    public static void simulate(int level, int r, int c, int cnt) {
    	
        //벽은 3개 짓습니다.
    	if(cnt == 3) {
    		BFS();
    		return ;
    	}
    	if( c >= M) {
    		c = 0;
    		r = r + 1;
    	}
    	
    	if(r >= N) {
    		return ;
    	}

    	//만약 빈칸 : 0 이라면 해당 칸에 벽을 둘 수 있습니다.
    	if(map[r][c] == 0) {
    		map[r][c] = 1;
    		simulate(level + 1, r, c + 1, cnt + 1);
    		map[r][c] = 0;
    	}
    	
    	//빈칸이든 아니든, 다음 칸으로 넘어가도록 합니다.
    	simulate(level + 1, r, c + 1, cnt);
    }

    
    public static void BFS() {
    	int[] dx = {-1, 1, 0, 0};
    	int[] dy = {0, 0, -1, 1};
    	boolean[][] visited = new boolean[N][M];
    	int cnt = 0;
    	Queue<Node> q = new LinkedList<>();
    	for(Node v : virusQ) {
    		cnt += 1;
    		visited[v.r][v.c] = true; 
    		q.offer(v);
    	}
    	
    	
    	while(!q.isEmpty()) {
    		Node temp = q.poll();
    		for(int dir=0;dir<4;dir++) {
    			int nr = temp.r + dx[dir];
    			int nc = temp.c + dy[dir];
    			if(nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
    			if(visited[nr][nc] == true) continue;
    			if(map[nr][nc] == 1) continue;
    			cnt += 1;
    			visited[nr][nc] = true;
    			q.offer(new Node(nr, nc));
    		}
    	}
    	
    	answer = Math.min(answer, cnt);
    }
}

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

 

BFS 대신 DFS Virus함수로 깊이우선탐색을 진행한경우입니다.

package algorhythm;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
	
	public static int N, M, result = 0;
	public static int[][] map;
	public static int[][] temp;
	public static int[] dx = {-1,0,1,0};
	public static int[] dy = {0,-1,0,1};
	public static int count=0;
	
   public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
	    M = sc.nextInt();
		map = new int[N][M];
		temp = new int[N][M];
		
		for(int i=0;i<N;i++) {
			for(int j=0;j<M;j++) {
				map[i][j] = sc.nextInt();
			}
		}
		
		dfs(0);
		System.out.println(result);
		
	}
   
   public static void dfs(int count) {
	   //울타리가 3개 설치된경우
	   if(count == 3) {
		   for(int i=0;i<N;i++) {
			   for(int j=0;j<M;j++) {
				   temp[i][j] = map[i][j];
			   }
		   }
		   
		   //각 바이러스의 위치에서 전파진행
		   for(int i=0;i<N;i++) {
			   for(int j=0;j<M;j++) {
				   if(temp[i][j] == 2) {
					   virus(i,j);
				   }
			   }
		   }
		   
		   //안전여역의 최대값계산
		   result = Math.max(result,  getScore());
		   return ; 
	   }
	   
	   //빈공간에 울타리를 설치
	   for(int i=0;i<N;i++) {
		   for(int j=0;j<M;j++) {
			   if(map[i][j] == 0) {
				   map[i][j] = 1;
				   count += 1;
				   dfs(count);
				   map[i][j] = 0;
				   count -= 1;
				   
			   }
		   }
	   }
   }
   
   public static void virus(int x, int y) {
	   for(int i=0;i<4;i++) {
		   int nx = x+ dx[i];
		   int ny = y+ dy[i];
		   if(nx>=0 && nx<N  && ny>=0 && ny <M) {
			   if(temp[nx][ny] == 0) {
				   temp[nx][ny] = 2;
				   virus(nx, ny);
			   }
		   }
	   }
   }
   
    public static int getScore() {
    	int score = 0;
    	for(int i=0;i<N;i++) {
    		for(int j=0;j<M;j++) {
    			if(temp[i][j] == 0) {
    				score += 1;
    			}
    		}
    	}
    	return score;
    }
    
    
   
   
}