백준 알고리즘 - 14502_연구소

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

문제 설명

0은 빈칸, 1은 벽, 2는 바이러스이다.
연구소는 N × M 크기의 직사각형이며, 일부 칸의 바이러스는 인접한 상하좌우로 퍼져나갈 수 있다.
또한 바이러스는 벽을 통과할 수 없다.
벽을 세운 후, 바이러스가 퍼져나갈 수 없는 곳을 안전영역이라 할때, 안전영역 크기의 최댓값을 구하라.

전체 코드

import java.util.*;

public class Practice {
	static Scanner sc = new Scanner(System.in);
	static int y, x;
	static int[][] map;
	static int[][] copyOfMap;
	static List<Coordinate> virusCoord = new ArrayList<>();
	static int[] dy = {-1, 1, 0, 0};
	static int[] dx = {0, 0, -1, 1};
	static int maxNumberOfBlank = 0;
	
	public static class Coordinate{
		int y;
		int x;
		public Coordinate(int y, int x) {
			this.y = y;
			this.x = x;
		}
	}
	
	public static void main(String[] args) {
		//1. 입력받으며 바이러스의 위치를 List에 저장
		readInput();
		
		copyOfMap(map);
		
		//2. 벽을 세운다
		dfs(0);
		
		System.out.println(maxNumberOfBlank);
	}

	private static void copyOfMap(int[][] tempMap) {
		copyOfMap = new int[y][x];
		for(int i = 0; i < y; i++) {
			for(int j = 0; j < x; j++) {
				copyOfMap[i][j] = tempMap[i][j];
			}
		}
	}

	private static void dfs(int depth) {
		
		if(depth == 3) {//4. 벽 3개 세우면 바이러스 확산
			bfs();
			return; // bfs로 탐색을 끝낸 후, 해당 depth의 dfs도 탐색을 끝내야함
		}
		
		//3. 모든 경우의 수를 돌며 벽 세움
		for(int i = 0; i < y; i++) {
			for(int j = 0; j < x; j++) {
				
				if(copyOfMap[i][j] == 0) {
					copyOfMap[i][j] = 1;
					dfs(depth + 1);
					copyOfMap[i][j] = 0; //dfs()가 탐색을 끝마친 후, 다음 케이스의 탐색을 위해 다시 0으로 돌려놓는다.
				}
				
			}
		}
	}

	private static void bfs() {
		//5. 맨 처음 주어진 바이러스('2')를 중심으로 퍼뜨리기
		//6. 바이러스 퍼뜨릴 맵 복사
		int[][] copyOfMap2 = new int[y][x];
		for(int i = 0; i < y; i++){ 
			for(int j = 0; j < x; j++) {
				copyOfMap2[i][j] = copyOfMap[i][j];
			}
		}
		
		//7. 최초에 주어진 바이러스 좌표 q에 넣기
		Queue<Coordinate> q = new LinkedList<>();
		for(int i = 0; i < virusCoord.size(); i++) {
			q.offer(virusCoord.get(i));
		}
		
		//8. 좌표가 들어있는 q에서 하나씩 좌표꺼내며 네방향 탐색
		//좌표값 0인 경우 바이러스가 퍼질 수 있음
		Coordinate coord;
		while(!q.isEmpty()) {
			coord = q.poll();
			
			int ny;
			int nx;
			for(int d = 0; d < 4; d++) {
				ny = coord.y + dy[d];
				nx = coord.x + dx[d];
				
				if(isArrange(ny, nx) && copyOfMap2[ny][nx] == 0) {
					copyOfMap2[ny][nx] = 2;
					q.offer(new Coordinate(ny, nx));
				}
			}
		}
		
		//9. 탐색종료 후 0의 개수 세기
		int numberOfBlank = 0;
		for(int i = 0; i < y; i++) {
			for(int j = 0; j < x; j++) {
				if(copyOfMap2[i][j] == 0) {
					numberOfBlank++;
				}
			}
		}
		
		//10. 최대인지 비교하기
		maxNumberOfBlank = Math.max(maxNumberOfBlank, numberOfBlank);
	}
	
	private static boolean isArrange(int ny, int nx) {
		return ny >= 0 && nx >= 0 && ny < y && nx < x;
	}

	private static void readInput() {
		y = sc.nextInt();
		x = sc.nextInt();
		map = new int[y][x];
		
		for(int i = 0; i < y; i++) {
			for(int j = 0; j < x; j++) {
				map[i][j] = sc.nextInt();
				
				if(map[i][j] == 2) {//바이러스가 입력되면 좌표를 virusCoord에 저장
					virusCoord.add(new Coordinate(i, j));
				}
			}
		}
		
		/*
		for(int i = 0; i < y; i++) {
			for(int j = 0; j < x; j++) {
				System.out.print(map[i][j]);
			}
			System.out.println();
		}*/
	}

}

문제 풀이

for(int i = 0; i < y; i++) {
	for(int j = 0; j < x; j++) {
		map[i][j] = sc.nextInt();
		if(map[i][j] == 2) {//바이러스가 입력되면 좌표를 virusCoord에 저장
			virusCoord.add(new Coordinate(i, j));
		}
	}
}

N과 M을 받고나서, 해당 좌표값이 2라면 virusCoord에 저장한다.

private static void copyOfMap(int[][] tempMap) {
	copyOfMap = new int[y][x];
	for(int i = 0; i < y; i++) {
		for(int j = 0; j < x; j++) {
			copyOfMap[i][j] = tempMap[i][j];
		}
	}
}

입력받은 map을 copyOfMap에 복사한다.
복제본에 여러 케이스의 벽을 세워야 하기 때문인데, 굳이 여기서는 복사를 안해도 됐을거 같다.

for(int i = 0; i < y; i++) {
	for(int j = 0; j < x; j++) {
				
		if(copyOfMap[i][j] == 0) {
			copyOfMap[i][j] = 1;
			dfs(depth + 1);
			copyOfMap[i][j] = 0;
		}
				
	}
}

모든 copyOfMap을 돌면서 0인 경우에는 해당 인덱스에 1을 넣고 재귀함수를 호출한다.
dfs()에서 나온 후에는 다른 케이스의 벽을 세우기 위해 다시 0으로 돌려놔야 한다.

if(depth == 3) {//4. 벽 3개 세우면 바이러스 확산
	bfs();
	return; // bfs로 탐색을 끝낸 후, 해당 depth의 dfs도 탐색을 끝내야함
}

depth는 세운 벽의 수를 의미하며, 3이 되면 bfs()를 호출하여 바이러스를 확산시킨다.
return이 반드시 있어야 하는 이유는, bfs()에서 빠져나오게 되면 해당 depth의 dfs()는 반드시 종료되어야 하기 때문이다.

int[][] copyOfMap2 = new int[y][x];
for(int i = 0; i < y; i++){ 
	for(int j = 0; j < x; j++) {
		copyOfMap2[i][j] = copyOfMap[i][j];
	}
}

바이러스를 퍼뜨릴 map을 하나 더 복사한다. → copyOfMap2
bfs()에서는 맵에 2를 퍼뜨린 후 0의 개수를 세주기 때문에, dfs()와 bfs()에서 사용하는 map은 반드시 따로여야 한다.

Queue<Coordinate> q = new LinkedList<>();
for(int i = 0; i < virusCoord.size(); i++) {
	q.offer(virusCoord.get(i));
}

q객체를 선언해, 최초 바이러스의 위치를 담는다.
바이러스는 처음 위치를 중심으로 퍼져나가기 때문이다.

Coordinate coord;
while(!q.isEmpty()) {
	coord = q.poll();
			
	int ny;
	int nx;
	for(int d = 0; d < 4; d++) {
		ny = coord.y + dy[d];
		nx = coord.x + dx[d];
				
		if(isArrange(ny, nx) && copyOfMap2[ny][nx] == 0) {
			copyOfMap2[ny][nx] = 2;
			q.offer(new Coordinate(ny, nx));
		}
	}
}

q가 빌때까지 좌표를 하나씩 꺼내면서 사방으로 탐색한다.
좌표값이 0일 경우, 2로 바꿔주며 바이러스를 퍼뜨린다.
그리고 다음 탐색을 위해 해당 좌표를 q에 넣는다.

0을 바로바로 2로 바꿔나가기 때문에 중복체크를 해줄 필요가 없다.

int numberOfBlank = 0;
for(int i = 0; i < y; i++) {
	for(int j = 0; j < x; j++) {
		if(copyOfMap2[i][j] == 0) {
			numberOfBlank++;
		}
	}
}

바이러스를 다 퍼뜨린 후, copyOfMap2에서 0의 갯수를 센다.

maxNumberOfBlank = Math.max(maxNumberOfBlank, numberOfBlank);

그리고 이전 탐색에서의 0의 갯수와 비교하여, 둘 중 더 큰 수를 maxNumberOfBlank에 담는다.

해당 bfs() 과정이 끝난 후엔, 호출 시점으로 돌아가 return에 의해 depth == 3인 dfs()를 종료한다.
그러면 depth == 2인 dfs()에서 이중포문을 돌면서 새로운 케이스의 벽을 세워 또다시 depth == 3인 dfs()를 호출하는 것을 반복한다.

Git gist 주소

https://gist.github.com/ysyS2ysy/86d6c34ef006aeb23ea3202b6c92786f