[오답노트] BOJ 14502: 연구소 - JAVA

---

출처 : https://www.acmicpc.net/problem/11066
난이도 : 골드 4
풀이날짜 : 2022-12-26

---

---

풀이

아이디어

이 문제는 단계를 다음과 같이 나눌 수 있다.

1. 벽을 세운다.
2. 벽이 3개 세워지면 바이러스를 퍼트린다.
3. 바이러스가 다 퍼지면 안전공간을 세준다.

이것을 각 단계 별로 풀면
'1. 벽을 세운다' 문제는 백트래킹으로 문제를 풀 수 있다. 벽을 세우거나? 벽을 세우지 않거나로 나누어서 넘어가면 된다.

'2. 벽이 3개 세워지면 바이러스를 퍼트린다.' depth가 3이 되면 바이러스를 퍼트리는데 이는 bfs로 문제를 풀 수 있습니다.
바이러스들을 queue에 담고 바이러스를 사방탐색을 통해 감염시킵니다.

'3. 바이러스가 다 퍼지면 안전공간을 세준다.' queue가 다 비워지면 안전 공간을 세주면 된다.

---

코드

1차 코드(정답)

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

public class No14502 {

	static int N, M, ans;
	static int[][] mat;
	static int[] dirx = {-1, 0, 1, 0};
	static int[] diry = {0, -1, 0, 1};
	public static void main(String[] args) throws IOException {
		// 입력 받기
		input();
		pro();
		
	}
	
	private static void pro() {
		ans = 0;
		// dfs로 벽 세우기
		dfs(0,0,0);
		System.out.println(ans);
	}

	// 벽 세우기
	private static void dfs(int i, int j, int depth) {
		if(i>=N)
			return;
		// 벽이 3개 세워지면 체크한다.
		if(depth == 3) {
			check();
			return;
		}
		
		// 다음 행으로 넘어가기
		if(j==M) {
			dfs(i+1, 0, depth);
			return;
		}
		
		// 벽을 세울 수 있는 곳이면 벽을 세운다
		if(mat[i][j]==0) {
			mat[i][j]=1;
			dfs(i, j+1, depth+1);
			mat[i][j]=0;
		}
		
		// 벽을 세우지 않고 다음으로 넘어간다.
		dfs(i, j+1, depth);
	}

	// 이제 바이러스 퍼트리기 bfs로 풀기
	private static void check() {
		// 이렇게 벽이 세워진 경우에는 어떻게 퍼지는지를 세주기 위한 배열
		int[][] temp = new int[N][M];
		
		for(int i=0; i<N; i++)
			temp[i] = mat[i].clone();
		
		// 바이러스들을 큐에 넣기
		Queue<int[]> queue = new LinkedList<int[]>();
		
		// 바이러스를 큐에 넣기
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(temp[i][j] == 2) {
					queue.add(new int[] {i, j});
				}
			}
		}
		
		// 큐에 바이러스들을 넣기
		while(!queue.isEmpty()) {
			// 앞에거 꺼내기
			int[] cur = queue.poll();
			
			// 4방 탐색
			for(int di=0; di<4; di++) {
				int nx = cur[0] + dirx[di];
				int ny = cur[1] + diry[di];
				
				// 범위를 넘어가면 넘김
				if(nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
				// 전염이 되지 않는 곳이면 넘어간다.
				if(temp[nx][ny] != 0) continue;
				// 감염!
				temp[nx][ny] = 2;
				// 감염된 애를 큐에 넣어주기
				queue.add(new int[] {nx, ny});
			}
		}
		
		// 안전공간을 세주기
		int count = 0;
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(temp[i][j]==0)
					count++;
			}
		}
		// 가장 큰 안전공간을 저장해야 한다.
		ans = Math.max(ans, count);
	}

	// 입력
	private static void input() 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());
		
		mat = new int[N][M];
		
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<M; j++) {
				mat[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		br.close();
	}
}

코드는 옳았으나 visit여부를 넣고 안 넣고의 차이가 있다는 것이 밝혀졌다.

2차 풀이(visit처리: 정답)

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

public class No14502 {

	static int N, M, ans;
	static int[][] mat;
	static int[] dirx = {-1, 0, 1, 0};
	static int[] diry = {0, -1, 0, 1};
	public static void main(String[] args) throws IOException {
		// 입력 받기
		input();
		pro();
	}
	
	private static void pro() {
		ans = 0;
		// dfs로 벽 세우기
		dfs(0,0,0);
		System.out.println(ans);
	}

	// 벽 세우기
	private static void dfs(int i, int j, int depth) {
		if(i>=N)
			return;
		// 벽이 3개 세워지면 체크한다.
		if(depth == 3) {
			check();
			return;
		}
		
		// 다음 행으로 넘어가기
		if(j==M) {
			dfs(i+1, 0, depth);
			return;
		}
		
		// 벽을 세울 수 있는 곳이면 벽을 세운다
		if(mat[i][j]==0) {
			mat[i][j]=1;
			dfs(i, j+1, depth+1);
			mat[i][j]=0;
		}
		
		// 벽을 세우지 않고 다음으로 넘어간다.
		dfs(i, j+1, depth);
	}

	// 이제 바이러스 퍼트리기 bfs로 풀기
	private static void check() {
		// 이렇게 벽이 세워진 경우에는 어떻게 퍼지는지를 세주기 위한 배열
		int[][] temp = new int[N][M];
		
		for(int i=0; i<N; i++)
			temp[i] = mat[i].clone();
		
		// 바이러스들을 큐에 넣기
		Queue<int[]> queue = new LinkedList<int[]>();
		
		// 왔던 곳인지 본다.
		// temp가 2인 경우를 봐도 된다. 그러나 시간이 다르다.
		boolean[][] visit = new boolean[N][M];
		
		// 바이러스를 큐에 넣기
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(temp[i][j] == 2) {
					queue.add(new int[] {i, j});
					visit[i][j] = true;
				}
			}
		}
		
		// 큐에 바이러스들을 넣기
		while(!queue.isEmpty()) {
			// 앞에거 꺼내기
			int[] cur = queue.poll();
			
			// 4방 탐색
			for(int di=0; di<4; di++) {
				int nx = cur[0] + dirx[di];
				int ny = cur[1] + diry[di];
				
				// 범위를 넘어가면 넘김
				if(nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
				// 이미 왔던 곳이면 넘어간다.
				if(visit[nx][ny]) continue;
				// 전염이 되지 않는 곳이면 넘어간다.
				if(temp[nx][ny] != 0) continue;
				visit[nx][ny] = true;
				// 감염!
				temp[nx][ny] = 2;
				// 감염된 애를 큐에 넣어주기
				queue.add(new int[] {nx, ny});
			}
		}
		
		// 안전공간을 세주기
		int count = 0;
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(temp[i][j]==0)
					count++;
			}
		}
		// 가장 큰 안전공간을 저장해야 한다.
		ans = Math.max(ans, count);
	}

	// 입력
	private static void input() 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());
		
		mat = new int[N][M];
		
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<M; j++) {
				mat[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		br.close();
	}
}

---

결과

visit 처리를 한 코드가 더 빠르게 해결 된 것을 알 수 있다.

---

느낀점

저번에 풀었던 때와 더 빠르고 좋은 풀이가 나오는 것을 알 수 있었다.

점점 나아지는 실력을 느끼고 더 열심히 해야겠다고 생각이 들었다.