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

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

1. 문제 링크

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

14502번: 연구소

 

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

1. 이 문제는 벽 3개를 세우는 케이스마다 각각 조사하여 안전영역의 최댓값을 계속 갱신해야 한다.

2. Input으로 연구소 정보에 대한 배열을 받을 때, 두 가지 배열을 사용한다.

   . board : 각 케이스별로 BFS를 수행할 때 사용할 연구소 정보

   . copyBoard : 각 케이스가 끝난 후 board를 초기화해줄 연구소 정보

3. 또한, 바이러스의 위치정보를 담을 Queue 두 개를 사용한다.

   . q : 각 케이스 별로 BFS를 수행할 때 사용할 Queue

   . copyQ : 각 케이스가 끝날 때마다 q를 초기화 해줄 Queue

4. 이 문제는 0(빈칸)인 칸 중에서 3개를 선택해야 하므로, Recursion을 통해 '조합(Combination)' 로직을 구현한다.

5. 조합 로직을 구현하기 위해, 벽을 놓을 수 있는 칸을 저장하는 ArrayList를 사용해야 한다. --> candidate

6. candidate에서 조합을 통해 3개를 고른 후, 벽을 설정하고 바이러스 큐를 통한 BFS를 수행한다.

7. BFS를 수행하고 나면, 안전지대(0)의 개수를 세고, 최댓값을 갱신해준다.

8. BFS와 count가 끝나면 아래 세 가지를 초기화해야 한다.

   . board를 copyBoard로 초기화

   . q를 copyQ로 초기화

   . visit을 false로 초기화

 

3. 코드

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

class Virus {
	int y, x;

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

}

public class Main {

	static int N, M;
	static int[][] board;
	static int[][] copyBoard; // 연구소의 초기 상태를 간직할 배열
	static boolean[][] visit;
	static int[] dirY = { 0, 0, -1, 1 };
	static int[] dirX = { 1, -1, 0, 0 };
	static Queue<Virus> q = new LinkedList<>();
	static Queue<Virus> copyQ = new LinkedList<>(); // 바이러스의 초기 위치를 간직할 Queue
	static ArrayList<Virus> selected = new ArrayList<>();
	static ArrayList<Virus> candidate = new ArrayList<>(); // 벽을 세울 후보 좌표를 저장할 ArrayList
	static int maxSafe = 0;

	// 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][M];
		visit = new boolean[N][M];
		copyBoard = new int[N][M];

		for (int i = 0; i < N; i++) {
			String[] line = br.readLine().split(" ");
			for (int j = 0; j < M; j++) {
				board[i][j] = Integer.parseInt(line[j]);
				copyBoard[i][j] = Integer.parseInt(line[j]);
				if (board[i][j] == 2) {
					q.add(new Virus(i, j));
					copyQ.add(new Virus(i, j));
				}
				if (board[i][j] == 0)
					candidate.add(new Virus(i, j));
			}
		}

		select(0, 0);
		System.out.println(maxSafe);

	}

	public static void select(int index, int depth) {
		if (depth == 3) {
			for (int k = 0; k < selected.size(); k++) {
				int sy = selected.get(k).y;
				int sx = selected.get(k).x;
				board[sy][sx] = 1;
			}

			BFS();
			count();
			reset();
			return;
		}

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

	}

	public static void reset() {
		// board 초기화
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				board[i][j] = copyBoard[i][j];
			}
		}
		// virusQ 초기화
		q.clear();
		q.addAll(copyQ);
		// visit 초기화
		visit = new boolean[N][M];
	}

	public static void BFS() {
		while (!q.isEmpty()) {
			Virus now = q.poll();
			int y = now.y;
			int x = now.x;
			visit[y][x] = true;
			for (int i = 0; i < 4; i++) {
				int yy = y + dirY[i];
				int xx = x + dirX[i];
				if (xx < 0 || yy < 0 || xx >= M || yy >= N || 
						board[yy][xx] == 1 || visit[yy][xx])
					continue;
				q.add(new Virus(yy, xx));
				visit[yy][xx] = true;
				board[yy][xx] = 2;
			}
		}
	}

	public static void count() {
		int temp = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (board[i][j] == 0)
					temp++;
			}
		}
		maxSafe = Math.max(temp, maxSafe);
	}

}

 

4. 채점 결과

 

5. 느낀 점

   . 수많은 케이스를 하나하나 조사해야 하는 문제이다.

   . 케이스를 조사할 때마다, 사용되는 배열, 큐를 초기화하는데 신경 써야 한다.

   . 다시 보니까 클래스를 Virus라고 하지 말고 Pair나 Loc으로 할 걸 그랬다.