📝 문제
14502번: 연구소
인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크
www.acmicpc.net
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
// 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 함
// 0 : 빈칸, 1: 벽, 2: 바이러스
public class Baek_14502 {
static int[] dx = {-1,0,1,0};
static int[] dy = {0,1,0,-1};
static int N,M;
static int[][] virusmap;
static int maxsafezone = Integer.MIN_VALUE; // 안전구역의 최대 개수를 위해 최솟값을 저장해둘 변수 설정
static void countWall(int wallcount) { // 벽(1)의 개수가 3개가 되면 안전구역을 찾을 함수(bfs)를 불러줄 함수(dfs)
if(wallcount == 3) {
countsafezone();
return; // 종료하고 재귀함수
}
for(int i=0; i<N; i++) {
for (int j = 0; j < M; j++) {
if(virusmap[i][j] == 0) {
virusmap[i][j] = 1;
countWall(wallcount+1);
virusmap[i][j] = 0; // 함수가 끝나면 다시 벽을 없애준다.
}
}
}
}
static void countsafezone() {
Queue<int[]> queue = new LinkedList<>();
for(int i=0; i<N; i++) {
for (int j = 0; j < M; j++) {
if( virusmap[i][j] == 2) { // 바이러스가 있는 곳이라면
queue.offer(new int[] {i,j});
}
}
}
int copyvirusmap[][] = new int[N][M];
for(int i=0; i<N; i++) {
copyvirusmap[i] = virusmap[i].clone(); // 배열의 깊은 복사 => 복사 배열이 수정된다해도 원본 배열에 영향을 주지 못함
}
while(!queue.isEmpty()) {
int[] now = queue.poll();
for(int i=0; i<4; i++) {
int nx = now[0] + dx[i];
int ny = now[1] + dy[i];
if(nx>=0 && ny>=0 && nx<N && ny<M && copyvirusmap[nx][ny] == 0) {
queue.offer(new int[] {nx,ny} );
copyvirusmap[nx][ny] = 2;
}
}
}
findsafezone(copyvirusmap);
}
static void findsafezone(int[][] copyvirusmap) {
int safezone = 0;
for(int i=0; i<N; i++) {
for (int j = 0; j < M; j++) {
if(copyvirusmap[i][j] == 0) {
safezone ++;
}
}
}
if(safezone > maxsafezone) {
maxsafezone = safezone;
}
}
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
virusmap = new int[N][M];
for(int i=0; i<N; i++) {
st = new StringTokenizer(bf.readLine());
for (int j = 0; j < M; j++) {
virusmap[i][j] = Integer.parseInt(st.nextToken());
}
}
countWall(0);
System.out.println(maxsafezone);
}
}
✅ 문제 접근
제약 조건부터 살펴보자
- M은 9보다 작은 수
- 빈 칸의 개수는 3개 이상
- 벽(1) 은 반드시 3개를 세운다.
코드에서 변수 & 함수 이름이 비슷해 헷갈릴 수 있기 때문에 각자 무엇인지 설명하자면
변수
- virusmap : 원본 배열
- copyvirusmap : 원본 배열을 "깊은복사" 한 복사 배열
- safezone : 바이러스가 퍼져있지 않은 구역의 수
- maxsafezone : safezone 의 최대 개수를 저장하는 변수
함수
- countwall() : 벽(1) 의 개수가 3개가 되면 countsafezone() 를 호출해줄 BFS 함수
- countsafezone() : 원본 배열을 망가뜨리지 않고 바이러스(2)를 퍼진 후 배열을 findsafezone()에 리턴할 DFS 함수
- findsafezone() : countsafezone() 에 받은 copyvirusmap에서 안전구역(0)의 개수를 세어서 maxsafezone 변수에 저장해주는 함수
❓ 앝은 복사 / 깊은 복사
- 앝은 복사 : 복사한 배열이 원래 배열의 주솟값을 가져온다.
- 단순한 변수 선언을 통한 복사의 형태로, 복사하려는 배열의 주솟값을 가져온다. 그래서 복사한 배열을 수정하게 될 경우, 원래 배열 또한 수정되는 결과를 얻게 된다.
ex) int[] a = {1,2,3};
int[] b = a; // 만약 b가 수정되면 a도 수정된다.
- 깊은 복사 : 복사한 배열이 원래 배열을 그대로 가져온다.
- 원래 배열을 그대로 가져와 새 배열에 덮어쓰기 하는 것
따라서 복사한 배열을 수정하더라도, 원래 배열이 수정되는 일은 없다.
ex) int[] a = {1,2,3};
int[] b = a.clone(); //b가 수정되더라도 a배열에는 영향이 없다.
코드에서 깊은 복사
int copyvirusmap[][] = new int[N][M];
for(int i=0; i<N; i++) {
copyvirusmap[i] = virusmap[i].clone(); // 배열의 깊은 복사 => 복사 배열이 수정된다해도 원본 배열에 영향을 주지 못함
}
- virusmap 의 행을 깊은복사로 배열을 복사한다.
📎 깃허브주소
'Java' 카테고리의 다른 글
[JAVA] 백준 2667 단지번호붙이기 (BFS, DFS) (2) | 2023.11.23 |
---|---|
[JAVA] 우선순위 큐(Priority Queue) (0) | 2023.08.19 |
[JAVA] 큐(Queue) (0) | 2023.08.17 |
[JAVA] 스택(Stack) / 카카오 크레인 인형 뽑기(KAKAO) (0) | 2023.08.13 |
[JAVA] 재귀(Recursion)함수 , 재귀(Recursion)호출 (0) | 2023.08.12 |