BOJ - 연구소 14502번 (JAVA)

❓ 문제 - 백준 연구소 14502번 - JAVA 풀이법

출처 

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

14502번: 연구소

 

 

 

📝 문제해결법

1. 이 문제의 핵심은 그래프탐색(BFS)과 조합(Combination)으로 해결하는 것이다.

• 문제에서 벽을 3곳에 둘 수 있으므로 처음 wall를 입력받을 때 빈칸(0)일 때의 인덱스 i,j를 연결리스트에 저장
• 해당 빈칸 위치 리스트에서 3개 조합으로 벽을 둘 수 있는 곳을 선정
• 해당 조합의 경우에서 BFS를 돌려 바이러스를 퍼지게 구현하기 때문에 map_copy로 map을 copy 하고 해당 조합의 위치에서 빈칸(0)을 벽(1)으로 바꿔줌
• 해당 3개의 벽을 뒀을 경우에서 바이러스가 퍼져나가는 것을 BFS로 구현
• 해당 조합의 경우에서 바이러스 다 퍼져나간 후  빈칸(0) 즉, 안전영역의 갯수를 check()함수를 통해 구해 계속 갱신하면서 안전영역의 최댓값 찾기

2. BFS 내에서 구현 방법

• BFS를 이용하여 4방향(북, 남, 서,동)로 탐색
• 모든 바이러스 위치에서 4방향 탐색하면서 만약 탐색한 범위가 벽(1)이라면 탐색 종료
• 만약 탐색한 범위가 방문하지 않고 빈칸(0)이면 바이러스가 퍼져나갈 수 있으므로 해당 값을 바이러스(2)로 바꾸고 해당 위치를 queue에 append 하며 해당 곳을 방문처리 하기

3. 느낀점

• 지난 번에 올린 파이썬 풀이와 로직은 동일해서 올리기 약간 머쓱하지만...
• 자바 풀이자들을 위해 다시 한번 정리해보았습니다.. (+저포함 ㅎㅎ)

💻 소스코드

// BOJ - 연구소(14502번)
// DFS + BFS

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

public class Main_14502 {
	public static int n, m, wall_cnt;
	public static int[][] map;
	public static int ans;
	public static class Node {
		int x;
		int y;
		public Node(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	public static ArrayList<Node> wall;
	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];
		wall = new ArrayList<>();
		
		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] == 0) {
					wall_cnt++;
					wall.add(new Node(i, j));
				}
			}
		}
		System.out.println(wall_cnt);
		ans = 0;
		combination(new int[3], 0, 0);
		System.out.println(ans);
	}
	
	public static void combination(int[] combi, int depth, int start) {
		if(depth == 3) {
			int[][] map_copy = new int[n][m];
			for(int i=0;i<n;i++) {
				map_copy[i] = map[i].clone();
			}
			for(int c:combi) {
				Node node = wall.get(c);
				map_copy[node.x][node.y] = 1;
		
			}
			
			boolean[][] visited = new boolean[n][m];
			for(int i=0;i<n;i++) {
				for(int j=0;j<m;j++) {
					if (!visited[i][j] && map_copy[i][j] == 2) {
						bfs(map_copy, visited, i, j);
					}
				}
			}
			

			int cnt = check(map_copy);
	
			ans = Math.max(ans, cnt);
			return;
		}
		
		for(int i=start;i<wall_cnt;i++) {
			combi[depth] = i;
			combination(combi, depth+1, i+1);
		}
	}
	
	public static int[] dx = {-1, 1, 0, 0};
	public static int[] dy = {0, 0, -1, 1};
	
	public static void bfs(int[][] map_copy, boolean[][] visited, int x, int y) {
		Queue<Node> q = new LinkedList<Node>();
		visited[x][y] = true;
		q.add(new Node(x, y));
		while(!q.isEmpty()) {
			Node node = q.poll();
			for(int d=0;d<4;d++) {
				int nx = node.x + dx[d];
				int ny = node.y + dy[d];
				if(0 <= nx && nx < n && 0 <= ny && ny < m) {
					if(!visited[nx][ny] && map_copy[nx][ny] == 0) {
						map_copy[nx][ny] = 2;
						visited[nx][ny] = true;
						q.add(new Node(nx, ny));
					}
				}
			}
		}
	
		

	}
	
	public static int check(int[][] map_copy) {
		int cnt = 0;
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				if(map_copy[i][j] == 0) {
					cnt++;
				}
			}
		}
		return cnt;
	}

}