백준 17142 연구소 3 - 삼성 SW 역량 테스트 기출

백준 17142 연구소 3  - 삼성 SW 역량 테스트 기출

1. 문제 링크

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

17142번: 연구소 3

 

2. 문제 해결에 대한 아이디어

1. 이 문제에서 생각해야하는 로직은 크게 2가지였다.

2. 바이러스를 놓을 수 있는 위치 중 M 개를 골라 각 케이스 별로 조사해야 한다.

   . 이는 조합을 활용하여 쉽게 해결할 수 있다.

   . 한 케이스가 끝난 후 연구소 배열과 방문 배열을 초기화해줘야 한다.

3. 비활성 바이러스는 이미 전파되어 있는 것으로 생각해야 한다.

   . 비활성 바이러스라는 표식을 따로 한다. (나는 3으로 값을 바꿨다.)

   . 각 케이스마다의 전파 시간을 조사할 때, 비활성 바이러스 위치의 가중치는 제외한다.

 

3. 코드

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

public class Main {

	static int N, M;
	static int[][] board;
	static int[][] initBoard; // 경우의 수 한 케이스를 돌고나서 처음 상태로 리셋해줘야함
	static int[][] visit;
	static Queue<Virus> q = new LinkedList<>(); // BFS 돌릴 큐 
	static List<Virus> vList = new ArrayList<>();
	static List<Virus> candidate = new ArrayList<>(); // 경우의 수에서 활성화된 바이러스가 저장되는 리스트 
	static int[] dirY = { 0, 0, 1, -1 };
	static int[] dirX = { 1, -1, 0, 0 };
	static int minSec = 999999999;

	// 0은 빈칸 1은 벽 2가 바이러스를 놓을 수 있는 위치
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] nm = br.readLine().split(" ");
		N = Integer.parseInt(nm[0]);
		M = Integer.parseInt(nm[1]);

		board = new int[N][N];
		initBoard = new int[N][N];
		visit = new int[N][N];

		for (int i = 0; i < N; i++) {
			String[] lines = br.readLine().split(" ");
			for (int j = 0; j < N; j++) {
				board[i][j] = Integer.parseInt(lines[j]);
				initBoard[i][j] = Integer.parseInt(lines[j]);

				if (board[i][j] == 2)
					 // 경우의 수를 뽑기위해 모든 바이러스의 위치를 저장한다
					vList.add(new Virus(i, j));
			}
		}

		select(0, 0);
		if (minSec == 999999999)
			System.out.println(-1);
		else
			System.out.println(minSec);
		br.close();

	}

	public static void reset() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				board[i][j] = initBoard[i][j];
			}
		}
		visit = new int[N][N];
	}

	public static void select(int depth, int index) {
		if (depth == M) {
			q.addAll(candidate);
			for (int i = 0; i < candidate.size(); i++) {
				 // 현재 활성화된 바이러스에 대해 방문처리(1)을 해준다
				visit[candidate.get(i).y][candidate.get(i).x] = 1;
			}
			BFS();
			int cnt = 0;
			boolean success = true; // 빈칸 없이 모두 감염되었는지 여부 
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (board[i][j] == 0) {
						success = false;
						break;
					}
					if (board[i][j] != 3)
						 // 3은 비활성화였다가 활성화된 바이러스들로 전파시간에서 포함시키지 않는다
						cnt = Math.max(cnt, visit[i][j]);
				}
			}

			if (success) {
				minSec = Math.min(minSec, cnt - 1);
			}
			reset();
			return;
		}

		for (int i = index; i < vList.size(); i++) {
			candidate.add(vList.get(i));
			select(depth + 1, i + 1);
			candidate.remove(candidate.size() - 1);
		}
	}

	public static void BFS() {
		while (!q.isEmpty()) {
			Virus now = q.poll();
			int y = now.y;
			int x = now.x;

			for (int i = 0; i < 4; i++) {
				int yy = y + dirY[i];
				int xx = x + dirX[i];
				if (yy < 0 || xx < 0 || yy >= N || xx >= N || 
						board[yy][xx] == 1 || visit[yy][xx] != 0)
					continue;

				if (board[yy][xx] == 2 && visit[yy][xx] == 0) { 
					 // 비활성화에서 활성으로 바뀐 바이러스는 3으로 마킹한다
					board[yy][xx] = 3;
				} else if (board[yy][xx] == 0) {
					board[yy][xx] = 2;
				}
				visit[yy][xx] = visit[y][x] + 1;
				q.add(new Virus(yy, xx));

			}

		}

	}
}

class Virus {
	int y, x;

	public Virus(int y, int x) {
		super();
		this.y = y;
		this.x = x;

	}

}

 

4. 채점 결과

 

5. 느낀 점

1. 처음에 비활성 바이러스가 이미 전파된 것으로 고려하지 않아 틀렸었다.

2. 비활성 바이러스를 전파된 것으로 고려하며 전파시간을 계산하는 방법이 바로 안 떠올랐다.