[백준 - Java] 14502번 : 연구소 (삼성 SW 역량 테스트 기출 문제)

문제

www.acmicpc.net/problem/14502

14502번: 연구소

설명

안전 영역 크기의 최댓값을 얻는 것이 목표.

 

그러기 위해선 1. 연구소에 3개의 벽을 세울 수 있는 모든 경우를 따진다.

각 경우에 따라 2. 바이러스를 퍼뜨린 뒤, 3. 가장 안전 영역이 큰 경우를 구해야 한다.

 

main 메서드 - 연구소 map 구성하기

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());

			if(map[i][j] == 2) { 
				virusList.add(new Point(i, j)); // 바이러스 List에 추가 
			}
		}
	}

	buildWall(0); // 벽 세우기 

	System.out.println(ans); // 정답 출력 
}

 

연구소는 N * M의 int값을 저장하는 이차원 배열 (값 : 0 - 빈칸 / 1 - 벽 / 2 - 바이러스)로 구성된다.

 

매번 바이러스를 퍼뜨릴 때마다 map을 돌며 바이러스를 찾는 번거로움을 없애기 위해, 애초에 바이러스의 위치를 ArrayList에 추가했다.

 

map과 바이러스 리스트를 구성했다면

 

본격 적으로 벽 세우기 함수를 호출해 벽을 세운다.

 

1. 3개의 벽 세우기

이차원 배열에서 3개의 공간을 벽으로 만들어준다고 생각하면 쉽다.

즉 이차원 배열의 공간이 n개 일 때, 이 n개 중에서 3개를 뽑는 조합이라고 생각하면 된다.

 

* 조합에 대해 알고 싶다면, 아래 조합 포스팅 참고 

[Java] 조합 Combination

 조합을 통해서 모든 3개의 벽을 세우는 경우의 수를 얻는다.

 

백트래킹의 방법으로 조합을 구해 벽을 세울 것이다.

1차원과는 다르게 2차원 배열에서의 조합이기 때문에 이중 for문으로 (0, 0)부터 (n, n)까지 돌면서 구한다.

 

//벽 세우기 
//모든 벽을 세우는 조합을 구하기 위해 DFS 사용 - N*M개중 빈칸(0)인 것들 중에 3개를 뽑는 조합이라고 생각하면 됨 
public static void buildWall(int depth) { 
	if(depth == 3) { //3개의 벽을 다 세웠다면 
		copyMap = copy(map); // 이전 맵을 기억하기 위해 맵 복사 
		spreadVirus(); // 바이러스 퍼뜨리기 
		return;
	}

	for(int i = 0; i < N; i++) {
		for(int j = 0; j < M; j++) {
			if(map[i][j] == 0) {
				map[i][j] = 1; // 벽을 세우는 경우 
				buildWall(depth + 1);
				map[i][j] = 0; // 벽을 세우지 않는 경우 
			}
		}
	}
}

 

* 이중 for문 말고도, 0부터 n*m까지 (i/m, i% m)을 좌표로 하면 전체 2차원 배열을 탐색할 수 있다.

예를 들어 n = 3, m = 2인 3 * 2인 이차원 배열을 탐색한다면 아래와 같이 인덱스에 대한 좌표를 표현할 수 있다.

 

인덱스 i	(i / m, i % m)	(x, y)
0	(0/2, 0%2)	(0, 0)
1	(1/2, 1%2)	(0, 1)
2	(2/2, 2%2)	(1, 0)
3	(3/2, 3%2)	(1, 1)
4	(4/2, 4%2)	(2, 0)
5	(5/2, 5%2)	(2, 1)

 

조합을 통해 3개의 벽을 세웠다면, 이를 바탕으로 바이러스를 퍼뜨러야한다.

 

하지만 기존 연구소 map에 바로 바이러스를 퍼뜨리면 안 된다!!

재귀를 통해 3개의 벽을 계속 세우고 있기 때문에, 재귀가 끝날 때는 다시 원상태의 map으로 만들어야 된다.

(바이러스 퍼뜨려서 map을 바꿔버리면, 다음 조합을 구하는 단계에서 바뀐 map을 사용하게 됨)

※ 기존 연구소 map 복사하기!

따라서 기존 map을 복사한 copyMap으로 바이러스를 퍼뜨리고 안전 영역을 구한다!

 

2차원 배열은 clone()과 같은 메서드로 복사되지 않는다.

깊은 복사를 통해 복사를 해주어야 한다. 아니면 일일이 이중 for문으로 값을 넣어주어도 무방.

 

* 배열 복사의 경우 아래 포스팅을 참고해주세요.

coding-factory.tistory.com/548

//map 복사 
public static int[][] copy(int[][] arr) { // 2차원 배열 깊은 복사 
	int[][] copy = new int[N][M];
	for(int i = 0; i < arr.length; i++) {
		System.arraycopy(arr[i], 0, copy[i], 0, arr[i].length);
	}
	return copy;
}

 

2. 바이러스 퍼뜨리기

바이러스를 퍼뜨리는 과정은 BFS를 통해 구현한다.

바이러스가 있는 좌표를 중심으로 인접한 빈칸을 타고 타고 바이러스를 퍼뜨리기 때문.

 

바이러스는 상하좌우 인접한 빈칸으로 모두 퍼져나간다.

* 이차원 배열에서 상하좌우 이동 팁!

2차원 배열에서 상 하 좌 우 이동해야 하는 경우가 알고리즘 문제에서 종종 나온다.

이때 x, y 이동을 편리하게 하기 위해 dx, dy 배열을 만들어 두면 좋다.

 

 

인덱스 0, 1, 2, 3의 순으로 상, 좌, 하, 우라고 외우면 좋다.

위의 그림에서 상은 (-1, 0)부터 시작하고 반시계 방향으로 우까지 돌아가는 순이다.

이를 배열로 나타내면 아래와 같다. 

 

 

 

예를 들어 현재 2차원 배열의 (2, 2)를 기준으로 

위쪽으로 가려면 (2, 2) + (-1, 0) => (1, 2)

왼쪽은 (2, 2) + (0, -1) => (2, 1)

아래쪽은 (2, 2) + (1, 0) => (3, 2)

오른쪽은 (2, 2) + (0, 1) => (2, 3) 

이런 식으로 dx, dy의 방향에 따른 인덱스 값을 현재 좌표 값에 더해서 위치를 간단히 이동시킬 수 있다!

 

 

 

[Java] BFS 너비 우선 탐색 - 인접리스트 / 인접행렬로 구현

 

복사된 copyMap에서 BFS를 구현하기 위해 Queue를 만들어준다.

Queue에는 방문할 바이러스들을 넣어준다.

 

본격적으로 Queue가 빌 때까지 바이러스를 퍼뜨려나간다.

 

Queue에서 바이러스 하나를 꺼내 x, y좌표를 저장해준다.

x, y 좌표를 바탕으로 for문을 통해 상 좌 하 우 인접한 칸들을 검사한다.

map의 경계를 넘지 않는 선에서, 인접한 칸이 0 빈칸이라면 바이러스를 퍼뜨릴 수 있으므로 2로 만들어 주고,

바이러스가 된 이전의 빈칸의 좌표를 다시 큐에 넣어준다.

이를 큐가 빌 때까지 반복한다. 

 

큐가 다 소진되고, 바이러스가 다 퍼뜨려졌다면 안전 영역 크기를 구한다. 

 

//바이러스 퍼뜨리기 
public static void spreadVirus() {
	Queue<Point> queue = new LinkedList<>();

	for(int i = 0; i < virusList.size(); i++) { // 바이러스들 큐에 넣어줌 
		queue.add(virusList.get(i));
	}

	while(!queue.isEmpty()) {
		int x = queue.peek().x;
		int y =  queue.poll().y;

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

			// map 경계를 넘지 않는 선에서, 빈칸을 만난다면 바이러스 퍼뜨림 
			if(nx >= 0 && nx < N && ny >= 0 && ny < M && copyMap[nx][ny] == 0) {
				copyMap[nx][ny] = 2;
				queue.add(new Point(nx, ny));
			}
		}
	}

	getSafeArea(copyMap); // 안전 영역 구하기 
}

 

3. 안전 영역 크기 구하기 

copyMap을 전체 순회하며 0 빈칸을 발견한다면,  cnt 변수에 +1을 해주면서 안전 영역 크기를 구해나간다.

 

구해진 안전 영역 크기와 이전에 구했던 안전 영역 크기를 비교해, 큰 값을 새로운 ans 값으로 업데이트해준다.

//안전 영역(빈칸 0) 구하기 
public static void getSafeArea(int[][] copyWall) {
	int cnt = 0;
	for(int i = 0; i < N; i++) {
		for(int j = 0; j < M; j++) {
			if(copyWall[i][j] == 0) {
				cnt++;
			}
		}
	}

	ans = Math.max(ans, cnt);
}

전체 코드

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

public class Main {
	public static int[][] map;
	public static int[][] copyMap;
	public static int N, M;
	public static ArrayList<Point> virusList = new ArrayList<>();
	public static int[] dx = {-1, 0, 1, 0};
	public static int[] dy = {0, -1, 0, 1};
	public static int ans = 0;

	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());

				if(map[i][j] == 2) { // 매번 바이러스를 퍼뜨릴때마다 위치를 찾는 번거로움을 없애기 위해 애초에 바이러스의 위치를 List에 추가 
					virusList.add(new Point(i, j));
				}
			}
		}

		buildWall(0);

		System.out.println(ans);
	}

	//벽 세우기 
	public static void buildWall(int depth) { //모든 벽을 세우는 조합을 구하기 위해 DFS 사용 - N*M개중 빈칸(0)인 것들 중에 3개를 뽑는 조합이라고 생각하면 됨 
		if(depth == 3) { //3개의 벽을 다 세웠다면 
			copyMap = copy(map); // 이전 맵을 기억하기 위해 맵 복사 
			spreadVirus(); // 바이러스 퍼뜨리기 
			return;
		}

		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				if(map[i][j] == 0) {
					map[i][j] = 1; // 벽을 세우는 경우 
					buildWall(depth + 1);
					map[i][j] = 0; // 벽을 세우지 않는 경우 
				}
			}
		}
	}

	//map 복사 
	public static int[][] copy(int[][] arr) { // 2차원 배열 깊은 복사 
		int[][] copy = new int[N][M];
		for(int i = 0; i < arr.length; i++) {
			System.arraycopy(arr[i], 0, copy[i], 0, arr[i].length);
		}
		return copy;
	}

	//바이러스 퍼뜨리기 
	public static void spreadVirus() {
		Queue<Point> queue = new LinkedList<>();
		
		for(int i = 0; i < virusList.size(); i++) { // 바이러스들 큐에 넣어줌 
			queue.add(virusList.get(i));
		}

		while(!queue.isEmpty()) {
			int x = queue.peek().x;
			int y =  queue.poll().y;

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

				// map 경계를 넘지 않는 선에서, 빈칸을 만난다면 바이러스 퍼뜨림 
				if(nx >= 0 && nx < N && ny >= 0 && ny < M && copyMap[nx][ny] == 0) {
					copyMap[nx][ny] = 2;
					queue.add(new Point(nx, ny));
				}
			}
		}

		getSafeArea(copyMap);
	}

	//안전 영역(빈칸 0) 구하기 
	public static void getSafeArea(int[][] copyWall) {
		int cnt = 0;
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				if(copyWall[i][j] == 0) {
					cnt++;
				}
			}
		}

		ans = Math.max(ans, cnt);
	}
}

class Point {
	int x;
	int y;

	Point(int x, int y) {
		this.x = x;
		this.y = y;
	}
}

GITHUB

github.com/KwonMinha/BOJ/blob/master/BOJ%2314502/src/Main.java

KwonMinha/BOJ