[백준 17142] 연구소 3 (JAVA)

백준(BOJ) 17142 연구소 3

 

난이도
221217 기준 골드 3

사용 알고리즘
브루트포스
bfs

문제 링크
https://www.acmicpc.net/problem/17142

17142번: 연구소 3

 

 

풀이 과정

 

1. 문제 읽기(중요한 부분 굵게)

 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 1초가 걸린다. 승원이는 연구소의 바이러스 M개를 활성 상태로 변경하려고 한다.

 연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽, 바이러스로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다.

 예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자. 0은 빈 칸, 1은 벽, 2는 바이러스의 위치이다.

 

 연구소의 상태가 주어졌을 때, 모든 빈 칸에 바이러스를 퍼뜨리는 최소 시간을 구해보자.

 

입력

첫째 줄에 연구소의 크기 N(4 ≤ N ≤ 50), 놓을 수 있는 바이러스의 개수 M(1 ≤ M ≤ 10)이 주어진다.

둘째 줄부터 N개의 줄에 연구소의 상태가 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스를 놓을 수 있는 위치이다. 2의 개수는 M보다 크거나 같고, 10보다 작거나 같은 자연수이다.

 

출력

연구소의 모든 빈 칸에 바이러스가 있게 되는 최소 시간을 출력한다. 바이러스를 어떻게 놓아도 모든 빈 칸에 바이러스를 퍼뜨릴 수 없는 경우에는 -1을 출력한다.

 

2. 어떤 알고리즘을 사용할 것인가

 일단 문제를 읽어보면 비활성 바이러스 중 어떠한 M개의 활성 바이러스를 만드는 조합에 따라 최소 시간을 찾아낼 수 있을지를 알면 될 것 같습니다.

 따라서 브루트포스로 조합을 전부 찾고 각 조합마다 bfs로 최소시간을 찾아내는 방법을 쓸 수 있는지 검토해보겠습니다.

 

 연구소의 크기가 N*N이고 N의 최대 크기가 50이므로 최대 2500의 크기를 가질 수 있습니다.

처음 활성 바이러스를 만들 수 있는 개수는 최대 10개 입니다. 정확하지는 않지만 대략 10C5 (=252)가 나올 수 있는 조합의 수의 최대로 보입니다.

 각 조합에서 bfs를 돌린다고 쳤을때 대략 252 * 2500 = 630,000 번의 연산이 요구되므로 처음 생각 했던 대로 브루트포스와 bfs를 사용해도 시간초과가 나지 않을 것이라 판단하였고 따라서 해당 알고리즘을 이용하여 문제를 풀어보겠습니다.

 

3. 풀이 구상

1. 비활성 바이러스들의 위치가 들어있는 배열을 만들어서

2. 그 배열의 인덱스들로 조합을 짜고 

3. 조합에 들어있는 바이러스들을 활성화 시켰다고 가정하고 bfs를 돌려 최소시간을 구함

 

 처음에 문제를 읽을 때는 "활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다." 이 부분이 뭔가 포인트가 될 줄 알았는데 활성 바이러스가 빈칸으로 가나 비활성 바이러스 칸으로가나 똑같으니까 굳이 신경 쓸 필요는 없어보입니다.

 

여기까지 구상을 하고 코드를 작성해보겠습니다.

 

4. 코드 작성

1. 정답 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static int N, M;
	static int[][] initBoard;
	// 바이러스 좌표 리스트
	static List<RC> virusLs;
	static int minResult;
	
	// 좌표값 담을 클래스
	static class RC {
		
		int r;
		int c;
		
		public RC(int r, int c) {
			super();
			this.r = r;
			this.c = c;
		}
		
	}
	
    public static void main(String[] args) throws Exception {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	M = Integer.parseInt(st.nextToken());
    	
    	initBoard = new int[N][N];
    	virusLs = new ArrayList<>();
    	
    	for(int r = 0; r < N; r++) {
    		st = new StringTokenizer(br.readLine());
    		for (int c = 0; c < N; c++) {
    			int num = Integer.parseInt(st.nextToken());
    			initBoard[r][c] = num;
    			if(num == 2) {
    				virusLs.add(new RC(r,c));
    			}
			}
    	}
    	
    	minResult = Integer.MAX_VALUE;
    	combArr = new int[M];
    	// 조합
    	comb(0, 0);
    	
    	// 모두 바이러스 감염시키는 경우를 못찾아서 갱신이 안되는 경우
    	if(minResult == Integer.MAX_VALUE) {
    		bw.write("-1");
    	} else {
    		bw.write(minResult+"");
    	}
    	
    	bw.flush();
        bw.close();
        br.close();
    }
    
    static int[] combArr;
    
    static void comb(int cnt, int start) {
    	// 기저조건 M개 뽑으면 끝
    	if(cnt == M) {
    		// 매 combArr을 가지고 bfs해서 최소거리 구하기
    		bfs();
    		return;
    	}
    	
    	int virusCnt = virusLs.size();

    	for(int i = start; i < virusCnt; i++) {
    		combArr[cnt] = i;
    		comb(cnt+1,i+1);
    	}    	
    	
    }
    
    // 상하좌우
    static int[] dr = {-1,1,0,0};
    static int[] dc = {0,0,-1,1};
    
    static void bfs() {
    	// 이동 시간들을 담은 2차원 배열
    	// 기존 initBoard의 값은 안건드리고 steps에만 시간을 적어 visited의 역할도 같이 할 것
    	// visited의 역할을 하기위해 스텝을 1부터 시작하고 결과값에 1을 감소시킬것
    	// 0부터 시작하면 초기값 0과 구분이 안되어 visited의 역할을 못 함
    	int[][] steps = new int[N][N];
    	
    	Queue<RC> q = new LinkedList<>();
    	
    	for(int i = 0; i < M; i++) {
    		RC cur = virusLs.get(combArr[i]);
    		q.add(cur);
    		steps[cur.r][cur.c] = 1;
    	}
    	
    	while(q.size()>0) {

    		RC cur = q.poll();
    		
    		int curstep = steps[cur.r][cur.c];
    		
    		for(int d = 0; d < 4; d++) {
    			int nr = cur.r+dr[d];
    			int nc = cur.c+dc[d];
    		
    			// 연구소 범위 안에 있고 벽(1)이 아닌 경우
    			if(inRange(nr,nc) && initBoard[nr][nc] != 1) {
    				// 한번도 방문하지 않은 곳이면 curstep에 + 1 하고 큐에 추가
    				if(steps[nr][nc]==0) {
    					steps[nr][nc]=curstep+1;    						
    					q.add(new RC(nr,nc));
    				}
    			}
    		}
    		
    	}
    	
    	// 이번 조합에서 가장 오래걸리는 스텝을 확인
    	int maxStep = -1;
    	
    	for(int r = 0; r < N; r++) {
    		for(int c = 0; c < N; c++) {
    			// 바이러스(비활성)가 있는 칸이었다면 step을 1로 갱신
    			// 이걸 안해주면 maxStep계산할때 비활성 바이러스가 있는칸이 maxStep이 될 수도 있음
    			if(initBoard[r][c]==2) {
    				steps[r][c]=1;
    			}

    			// steps가 0인데 initBoard가 벽이 아닌경우 -> 감염이 안된 것
    			if(steps[r][c]==0 && initBoard[r][c]!=1) {
    				// 아무것도 안하고 끝내버리기
    				return;
    			}
    			maxStep = Math.max(maxStep, steps[r][c]);
    		}
    	}
    	
    	
    	// 1을 추가한채로 시작했으니 -1
    	minResult = Math.min(minResult, maxStep-1);
    	
    }
    
    static boolean inRange(int nr, int nc) {
    	if(nr >= 0 && nr < N && nc >= 0 && nc < N) {
    		return true;
    	} else {
    		return false;
    	}
    }
    
}

 

2. 주의할 점

 

 정답은 한 번에 맞추기는 했는데 코드를 작성하며 몇가지 멈칫했던 부분이 있습니다.

 

2-1. 조합 알고리즘 작성

 순열 조합 부분집합 등 완전탐색을 위한 알고리즘은 모든 알고리즘 풀이의 기본 중의 기본이지만 매번 작성할 때마다 헷갈립니다. 순열 조합 부분집합의 정확한 정의와 코드 작성법을 알고 있어야 특히나 기업 코딩테스트를 칠 때 시간 낭비할 일 없을 것입니다.

 

2-2. "활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다."

 이 부분은 풀이를 구상할 때는 큰 문제가 되지 않을거라 생각했는데 마지막에 각 조합에서의 최대 시간 구할 때 조금 신경 쓸 부분이 있습니다. 이 부분에 대한 처리를 어디서 할 지에 대한 고민을 좀 했습니다.

 

 

 

풀이 후기

 이 문제는 백준에 있는 삼성 SW역량테스트 문제집에 있는 문제입니다. 역시나 기업 코딩테스트는 기본기가 중요하구나 하는 생각을 했습니다. 순열, 조합, 부분집합은 조금 고통스럽더라도 여러번 복습하는게 답이라고 생각합니다.