난이도
골드 4
문제
접근 방법
1. 완전 탐색(Brute Force)과 DFS(깊이 우선 탐색) 사용
-
연구소에서 3개의 벽을 세울 수 있는 모든 조합을 찾기 위해 완전 탐색을 사용합니다.
-
맵의 크기가 최대 8x8로 제한되어 있으므로, 완전 탐색으로 모든 경우의 수를 검토하는 것이 가능하며 시간복잡도가 매우 높지 않습니다.
-
벽을 세우는 과정까지는 반복문을 사용하여 구현할 수도 있지만, 재귀를 이용하여 벽을 하나씩 세우기 위해 DFS를 사용할 수 있습니다.
2. 바이러스 퍼뜨리기 BFS
-
모든 경우의 수에 대해 3개의 벽을 세운 후, 바이러스를 퍼뜨립니다.
-
바이러스를 퍼뜨리는 방법으로는 BFS(너비 우선 탐색)를 사용하는 것이 좋습니다. 한 지점에서 시작한 후, 주위로 퍼지기 때문에, BFS로 각 위치에 바이러스를 퍼뜨리는 것이 합리적이기 때문입니다.
3. 안전 영역 계산
-
바이러스가 퍼진 후 안전 영역(0)의 크기를 구하고 기존 최대 크기와 비교하여 최댓값을 구합니다.
-
이 과정은 모든 경우의 수에 대해 시행하므로, 3개의 벽을 세울 수 있는 가장 큰 안전 영역을 찾을 수 있습니다.
이러한 접근 방식을 선택한 이유는 문제의 조건이 완전 탐색과 DFS, BFS를 이용하도록 유도하는 특성을 가지고 있기 때문입니다.
각 칸의 크기와 세울 수 있는 벽의 개수가 제한적이므로 주어진 시간 안에 효율적으로 답을 찾았을 수 있습니다.
또한, 깊이 우선 탐색과 너비 우선 탐색 기법은 그래프와 트리에서 경로를 찾거나 조합을 적용할 때 유리한 방법입니다.
Code
import java.io.*;
import java.util.*;
public class Main {
static int N, M, maxSafeArea = 0;
static int[][] map, tempMap;
// Quadrant 4 Direction
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
// input
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());
}
}
// Wall create 3 (벽 3개 지음)
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (map[i][j] == 0) {
// Wall Counting (벽 세우기)
map[i][j] = 1;
buildWall(1);
/*
벽을 3개 세우는 과정을 구현하기 위해 사용함.
예시를 보면, 처음에 서로 다른 3개의 빈 칸에 벽을 세우는 모든 경우의 수를 확인해야 하므로,
재귀 호출을 사용하여, 벽을 한 개씩 세워본 후 남은 벽을 모두 세운 경우 바이러스를 퍼뜨려본 다음 안전 구역의 크기를 구합니다.
해당 코드에서, buildWall(1)은 두 가지 의미가 있습니다.
1. 첫 번째 벽을 세운 상태에서 호출하였다.
2. 현재까지 1개의 벽을 세웠다.
다시말해,벽을 세우는 과정에서 재귀 함수를 호출할 때마다, cnt(현재까지 세운 벽의 개수)를 1씩 증가시킵니다.
모든 벽을 다 세웠다는 것은 cnt가 3이라는 뜻이며,
이 경우에 바이러스를 퍼뜨리는 작업을 진행합니다.
결론적으로, 즉, 이 코드는 벽을 세우는 재귀 함수의 시작점으로, 처음 벽을 세운 후 남은 벽들을 세우기 위해 재귀 함수를 호출하는 코드입니다.
이를 통해 가능한 모든 위치에 벽을 설치한 후, 안전한 영역의 최대 크기를 찾을 수 있습니다.
*/
// Wall reset
map[i][j] = 0;
}
}
}
// result, print
System.out.print(maxSafeArea);
}
// Wall Counting (벽 세우기 (재귀 호출이라고 보면됨.))
public static void buildWall(int cnt) {
if (cnt == 3) {
// instance 바이러스 퍼뜨리기
Virus v = new Virus();
v.spread(map);
maxSafeArea = Math.max(maxSafeArea, v.findSafeArea());
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(cnt + 1);
// 벽 초기화
map[i][j] = 0;
}
}
}
}
}
// virus class
class Virus {
int N = Main.N;
int M = Main.M;
int[] dx = Main.dx;
int[] dy = Main.dy;
// 바이러스 확산
public void spread(int[][] map) {
int[][] tempMap = new int[N][M];
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
tempMap[i][j] = map[i][j];
}
}
Queue<int[]> queue = new LinkedList<>(); //바이러스 확산가정을 BFS로 구현하기 위함.
/*
BFS는 탐색할 위치를 기록하고 처리하기 위해 큐(Queue)를 사용하는 것이 일반적입니다.
이 문제에서는 바이러스 위치를 큐에 저장하고 큐가 빌 때까지 바이러스 확산을 처리하기 위해 사용합니다.
Queue<int[]> queue = new LinkedList<>(); 대신 다른 구현 방법도 가능하지만,
자바에서는 큐를 구현할 때 주로 LinkedList를 사용하므로 이 방법이 가장 권장되는 방법입니다.
따라서, 이 코드는 BFS를 활용하여 바이러스를 확산시키기 위해 큐를 선언하고 초기화하는데
사용됩니다. 이 작업이 반드시 필요하지는 않지만, BFS를 사용하여 코드를 효율적으로 작성하는 데 도움이 됩니다.
*/
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (tempMap[i][j] == 2) {
queue.add(new int[]{i, j});
}
}
}
while (!queue.isEmpty()) {
int[] pos = queue.poll(); // 이건 자바 큐에서, 값 제거할 때 씀.
/*
여기서, remove()를 사용해도 되지만, 큐가 비어있는 경우 NoSuchElementException ERR
따라서, que가 비어있을 경우, null을 반환해주는 poll() use.
clear()은 큐 비우는 용도로 사용함.
*/
for (int i = 0; i < 4; i++) {
int nx = pos[0] + dx[i];
int ny = pos[1] + dy[i];
if (nx >= 0 && ny >= 0 && nx < N && ny < M) {
if (tempMap[nx][ny] == 0) {
tempMap[nx][ny] = 2;
queue.add(new int[]{nx, ny});
}
}
}
}
Main.tempMap = tempMap;
}
// 안전 영역 찾기
public int findSafeArea() {
int safeArea = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (Main.tempMap[i][j] == 0) {
safeArea++;
}
}
}
return safeArea;
}
}
코드 추가 설명
-
코드의 첫 부분에서는 N, M, maxSafeArea, map, tempMap, dx, dy와 같은 변수와 배열을 선언합니다. 이들은 문제 해결에 필요한 정보와 데이터를 저장하는 데 사용됩니다.
-
main 메서드에서는 입력을 받고, 초기 맵을 설정합니다. 이 때, map 배열에는 연구소의 상태가 저장됩니다.
-
이후, buildWall 메서드를 호출하여 벽을 세우는 과정을 시작합니다. 이 메서드는 재귀적으로 동작하며, 현재까지 세운 벽의 개수를 기록하는 cnt를 인자로 받습니다.
-
buildWall 메서드에서 cnt가 3이 되면, 즉 3개의 벽을 세운 상태일 때는 바이러스를 퍼뜨리고 안전 영역의 크기를 구하는 과정을 진행합니다.
-
spread 메서드는 바이러스를 퍼뜨리는 과정을 구현한 메서드입니다. tempMap을 사용하여 현재 상태를 저장하고, 큐를 이용하여 바이러스의 위치를 관리합니다. 상하좌우로 인접한 빈 공간에 바이러스를 퍼뜨립니다.
-
findSafeArea 메서드는 안전 영역의 크기를 계산합니다. tempMap에서 값이 0인 영역을 찾아 개수를 세어 반환합니다.
이렇게 코드가 구성되어 있습니다. 이 코드는 3개의 벽을 세우는 모든 경우를 확인하고, 바이러스를 퍼뜨려 안전 영역의 최대 크기를 찾는 문제를 해결합니다. 재귀 호출과 BFS(Breadth-First Search)를 활용하여 문제를 해결하도록 구현되어 있습니다.
(마지막 문단의 추가내용)
재귀 호출(Recursion)
재귀 호출은 함수가 자기 자신을 호출하는 것을 말합니다. 재귀 호출을 사용하면 복잡한 문제를 더 작은 하위 문제로 나누어 해결할 수 있습니다. 일반적으로 재귀 호출은 종료 조건을 설정하여 재귀적인 호출이 끝나도록 합니다. 이를테면, 특정 조건이 만족되었을 때 재귀 호출을 중단하고 결과값을 반환합니다. 이 문제에서 buildWall 메서드가 재귀 호출을 사용하여 가능한 모든 벽의 조합을 탐색하고 있습니다. 처음에는 첫 번째 위치에 벽을 세우고, 그 다음 위치에 벽을 세우는 식으로 조합을 만들어가며 재귀 호출을 수행합니다.
BFS(Breadth-First Search):
BFS는 너비 우선 탐색을 의미합니다. 그래프나 트리에서 가까운 노드부터 탐색하는 방식 중 하나입니다. BFS는 큐(Queue) 자료구조를 사용하여 구현됩니다. BFS는 레벨 단위로 탐색을 진행하며, 한 레벨의 모든 노드를 방문한 후 다음 레벨의 노드를 탐색합니다. 이 문제에서 Virus 클래스의 spread 메서드에서 BFS를 사용하여 바이러스를 퍼뜨리고 있습니다. 바이러스가 있는 위치를 큐에 넣고, 인접한 빈 공간으로 바이러스를 퍼뜨리는 과정을 반복하여 BFS를 구현합니다.
BFS는 최단 경로를 찾거나 상태 공간을 탐색하는 등 다양한 문제에 활용될 수 있습니다. 너비 우선 탐색의 특징은 같은 레벨의 노드를 모두 방문한 후 다음 레벨로 넘어간다는 점입니다. 이를 통해 가까운 노드부터 탐색하며 최적의 결과를 찾을 수 있습니다.
위의 코드를 좀더 최적화 하려면 ?
-
BFS에서 중복된 연산을 줄이기 위해 tempMap을 사용하는 대신에 map 배열을 직접 변경하고, BFS 탐색 시 방문 여부를 나타내는 배열을 추가로 사용합니다. 이렇게 하면 매번 tempMap을 복사하는 비용을 줄일 수 있습니다.
-
벽을 세우는 모든 경우의 수를 탐색할 때, 중복된 조합을 방지하기 위해 시작 위치를 기준으로 한정하여 탐색합니다. 예를 들어, (0, 0)부터 (N-1, M-1)까지의 모든 위치에서 벽을 세우는 경우를 고려하지 않고, (0, 0)부터 (N-3, M-1)까지의 범위 내에서만 벽을 세우도록 합니다.
-
매번 안전 영역의 크기를 계산하는 과정을 생략하고, 바이러스를 퍼뜨린 후 바이러스로 인해 감염되지 않은 영역의 개수를 바로 카운팅합니다. 이를 통해 중간 과정에서 필요한 변수와 연산을 줄일 수 있습니다.
import java.io.*;
import java.util.*;
public class Main {
static int N, M, maxSafeArea = 0;
static int[][] map;
// Quadrant 4 Direction
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
// input
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());
}
}
// Wall create 3 (벽 3개 지음)
buildWall(0, 0);
// result, print
System.out.print(maxSafeArea);
}
// buildWall(재귀 호출)
public static void buildWall(int count, int start) {
if (count == 3) {
// instance spread virus
Virus v = new Virus();
maxSafeArea = Math.max(maxSafeArea, v.spreadVirus());
return;
}
for (int i = start; i < N * M; i++) {
int x = i / M;
int y = i % M;
if (map[x][y] == 0) {
map[x][y] = 1;
buildWall(count + 1, i + 1);
map[x][y] = 0;
}
}
}
}
// virus class
class Virus {
int[][] tempMap;
int N, M;
int[] dx, dy;
public Virus() {
this.N = Main.N;
this.M = Main.M;
this.dx = Main.dx;
this.dy = Main.dy;
this.tempMap = new int[N][M];
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
tempMap[i][j] = Main.map[i][j];
}
}
}
// spread virus
public int spreadVirus() {
Queue<int[]> queue = new LinkedList<>();
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (tempMap[i][j] == 2) {
queue.add(new int[]{i, j});
}
}
}
while (!queue.isEmpty()) {
int[] pos = queue.poll();
for (int i = 0; i < 4; i++) {
int nx = pos[0] + dx[i];
int ny = pos[1] + dy[i];
if (nx >= 0 && ny >= 0 && nx < N && ny < M) {
if (tempMap[nx][ny] == 0) {
tempMap[nx][ny] = 2;
queue.add(new int[]{nx, ny});
}
}
}
}
int safeArea = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (tempMap[i][j] == 0) {
safeArea++;
}
}
}
return safeArea;
}
}
