[JAVA] 백준 14502 - 연구소

 

삼성 SW 역량 테스트 기출 문제 중 하나인 연구소 문제이다.

 

🤔 문제 접근

당연한 얘기지만 벽을 어떻게 세우느냐가 가장 중요한 포인트라고 생각했다.

하지만 벽을 세우는 기준을 잡기가 어려웠다.

 

[예제 1]

 

예제 1의 맵을 봤을 때, 왼쪽 상단의 바이러스인 2 의 오른쪽 [1,2] 과 아래 [2,1] 에 벽을 세우고,

마지막 벽은 좌표 [4,6]에 세우면 안전구역 넓이가 최대가 된다.

이것과 예제2, 3의 경우를 보고 바이러스인 2를 기준으로 그래프 탐색을 해야하는지

기존에 벽이었던 1에서 그래프 탐색을 통해 새로운 벽 3개를 세워야 할지 고민이었다.

 

✅ 핵심 풀이

위 고민의 답은 바로 "완전 탐색" 이었다.

기존 맵 전체를 확인하여 [i, j]의 좌표가 0 인 경우, 벽을 세울 수 있는 장소가 된다.

좌표가 0인 곳을 찾아 세울 수 있는 벽 3개 중 1개를 세우고 재귀를 통해

다음 벽을 세울 곳을 찾아야 했다.

벽 3가지를 전부 세웠다면 BFS를 통해 바이러스 (2) 를 퍼트렸을 때

안전구역 (0) 이 몇개가 있는지 카운트 해주면 된다.

 

🚨 CODE

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

public class Main {
	
	public static int n, m;
	public static int[][] map, clone;
	public static int[] dx = {1,-1,0,0};
	public static int[] dy = {0,0,1,-1};
	public static int max = Integer.MIN_VALUE;
    
	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());
			}
		}
		
		setWall(0);
		System.out.println(max);
	}
    
	public static void setWall(int count) {
		if(count == 3) {
			setVirus();
			return;
		}
		
		for(int i = 0; i<n; i++) {
			for(int j = 0; j<m; j++) {
				if(map[i][j] == 0) {
					map[i][j] = 1;
					setWall(count+1);
					map[i][j] = 0;
				}
			}
		}
	}
    
	public static void setVirus() {
		Queue<Node> q = new LinkedList<>();
		
		for(int i = 0; i<n; i++) {
			for(int j = 0; j<m; j++) {
				if(map[i][j] == 2) {
					q.add(new Node(i,j));
				}
			}
		}
		
		int[][] clone = new int[n][m];
		for(int i = 0; i<n; i++) {
			clone[i] = map[i].clone();
		}
		
		while(!q.isEmpty()) {
            Node now = q.poll();
            int x = now.x; 
            int y = now.y; 

            for(int k=0; k<4; k++) {
                int nx = x + dx[k];
                int ny = y + dy[k];

                if(0<=nx && nx<n && 0<=ny && ny<m) {
                    if(clone[nx][ny] == 0) {
                        q.add(new Node(nx,ny));
                        clone[nx][ny] = 2;
                    }
                }
            }
        }
		
		findSafeZone(clone);
	}
	
	public static void findSafeZone(int[][] clone) {
		int safe = 0;
		for(int i = 0; i<n; i++) {
			for(int j = 0; j<m; j++) {
				if(clone[i][j] == 0)
					safe++;
			}
		}
		if(max < safe) {
			max = safe;
		}
	}

	static class Node {
		int x;
		int y;
		Node(int x, int y){
			this.x = x;
			this.y = y;
		}
	}
}

 

✨ 느낀점

풀고 난 후 지도의 크기와 시간 제한을 통해 문제 풀이를 위한 알고리즘을

어느 정도 예상할 수 있지 않았을까 생각이 든다.

지도의 크기가 (3 ≤ N, M ≤ 8) 이므로 그 범위가 상당히 작고

따라서 벽을 세우는 좌표를 찾는 것이 완전 탐색일 것이라고 어느정도 

유추하고 풀었다면 이후부터는 쉽기 때문에 어렵지 않게 풀 수 있었을 지도 모른다.