문제 설명
14502번: 연구소
인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크
www.acmicpc.net
풀이 회고
제가 해당 문제를 풀기 위한 접근 방법은 다음과 같았습니다.
- 주어진 2차원 배열에 대해 임의의 3개의 벽 세우기
- 바이러스 확산시키기
- 안전 영역 크기 구하기(기존 값과 대소 비교 후 더 큰 값 할당)
- 변경된 2차원 배열 초기화하기
- 1번으로 돌아가 다시 임의의 3개의 벽 세우기(기존 3개의 벽과 완전히 중복되지 않는 3개의 벽)
위 단계에서 제가 가장 구현하기 까다로웠던 부분은 "임의의 3개의 벽을 세우는 것"이었습니다. 사실 DFS나 BFS를 통해 임의의 3개의 벽을 세우는 것을 구현하고자 했었으나, 결국 구현하지 못하고 (오랜 시간 삽질 끝에...😂) 가장 원시적인 방법인 다중 for문을 통해 구현하고 말았습니다. 이로 인해 엄청난 depth가 발생하고 말았습니다.. 🤣
다중 for문을 통한 임의의 3개 벽 세우기 로직은 백트래킹을 통해 로직을 단순화시킬 수 있었습니다. (2022. 7. 13.)
3개의 벽을 다 세우고 나면 바이러스를 확산시키도록 했는데, 이는 BFS를 통해 다소 평이하게 구현할 수 있었습니다. 바이러스의 x좌표, y좌표 값을 지니고 있는 Point 객체를 별도로 생성해준 후 빈 공간(0)을 만나면 그 자리를 또 다른 바이러스(2)로 채워주는 식으로 확산시켜나갔습니다.
그 이후에는 안전 영역의 크기를 2중 for문을 통해 구했고, 기존에 결과값으로 할당된 값과 대소 비교하여 더 큰 값을 할당시키도록 했습니다. 마지막으로 다시 새로운 3개의 벽을 세우고 재탐색을 하기 위해 당초에 입력받았었던 2차원 배열을 별도로 저장해놓아 이를 통해 바이러스로 가득한 2차원 배열을 초기화시켜주었습니다. 이후 다시 처음 단계로 돌아가 새로운 3개의 벽을 세우고 작업을 반복합니다. 최종적으로 더 이상 새로운 3개의 벽을 세울 수 없을 때 프로그램은 종료됩니다.
기존 코드를 최적화하였습니다. (2023. 3. 19.)
소스 코드(리팩토링 전)
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
class Main {
static int n, m;
static int[][] origin, hospital;
static int[] dx = {1, -1, 0, 0}, dy = {0, 0, 1, -1};
static int result = 0;
static class Point {
int x;
int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
public static void main(String[] args) {
init();
run();
System.out.println(result);
}
public static void init() {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
origin = new int[n][m];
hospital = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
origin[i][j] = sc.nextInt();
hospital[i][j] = origin[i][j];
}
}
}
public static void run() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (hospital[i][j] == 0) {
for (int k = 0; k < n; k++) {
for (int l = 0; l < m; l++) {
if (k == i && l == j) continue;
if (hospital[k][l] == 0) {
for (int o = 0; o < n; o++) {
for (int p = 0; p < m; p++) {
if (o == i && p == j || o == k && p == l) continue;
if (hospital[o][p] == 0) {
hospital[i][j] = 1;
hospital[k][l] = 1;
hospital[o][p] = 1;
spread();
int temp = countSafetyArea();
result = temp > result ? temp : result;
reset();
}
}
}
}
}
}
}
}
}
}
public static void spread() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (hospital[i][j] == 2) {
bfs(i, j);
}
}
}
}
public static void bfs(int x, int y) {
int nx, ny;
Queue<Point> queue = new LinkedList<>();
queue.add(new Point(x, y));
while (!queue.isEmpty()) {
Point point = queue.poll();
for (int i = 0; i < 4; i++) {
nx = point.x + dx[i];
ny = point.y + dy[i];
if (nx < 0 || nx > n - 1 || ny < 0 || ny > m - 1 || hospital[nx][ny] == 1
|| hospital[nx][ny] == 2) {
continue;
}
if (hospital[nx][ny] == 0) {
hospital[nx][ny] = 2;
queue.add(new Point(nx, ny));
}
}
}
}
public static int countSafetyArea() {
int countOfVirus = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (hospital[i][j] == 0) {
countOfVirus++;
}
}
}
return countOfVirus;
}
public static void reset() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
hospital[i][j] = origin[i][j];
}
}
}
}
리팩토링 소스 코드 (ver 2022. 7. 13.)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
class Main {
static int n, m;
static int[][] origin, hospital;
static int[] dx = {1, -1, 0, 0}, dy = {0, 0, 1, -1};
static int result = 0;
static class Point {
int x;
int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
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());
origin = new int[n][m];
hospital = new int[n][m];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < m; j++) {
origin[i][j] = Integer.parseInt(st.nextToken());
hospital[i][j] = origin[i][j];
}
}
run(0, 0);
System.out.println(result);
}
private static void run(int start, int depth) {
if (depth == 3) {
copy();
spread();
result = Math.max(result, countSafetyArea());
reset();
return;
}
int x, y;
for (int i = start; i < n * m; i++) {
x = i / m;
y = i % m;
if (hospital[x][y] == 0) {
hospital[x][y] = 1;
run(start + 1, depth + 1);
hospital[x][y] = 0;
}
}
}
private static void spread() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (hospital[i][j] == 2) {
bfs(i, j);
}
}
}
}
private static void bfs(int x, int y) {
int nx, ny;
Queue<Point> queue = new LinkedList<>();
queue.add(new Point(x, y));
while (!queue.isEmpty()) {
Point point = queue.poll();
for (int i = 0; i < 4; i++) {
nx = point.x + dx[i];
ny = point.y + dy[i];
if (nx < 0 || nx > n - 1 || ny < 0 || ny > m - 1 || hospital[nx][ny] == 1
|| hospital[nx][ny] == 2) {
continue;
}
if (hospital[nx][ny] == 0) {
hospital[nx][ny] = 2;
queue.add(new Point(nx, ny));
}
}
}
}
private static int countSafetyArea() {
int countOfVirus = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (hospital[i][j] == 0) {
countOfVirus++;
}
}
}
return countOfVirus;
}
private static void copy() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
origin[i][j] = hospital[i][j];
}
}
}
private static void reset() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
hospital[i][j] = origin[i][j];
}
}
}
}
리팩토링 소스 코드 (ver 2023. 3. 19.)
import java.io.*;
import java.util.*;
class Main {
static int[] dx = {1, -1, 0, 0}, dy = {0, 0, 1, -1};
static int n, m;
static int[][] hospital;
static List<int[]> viruses = new ArrayList<>();
static int blankCount = -3, result = 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());
hospital = new int[n][m];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < m; j++) {
hospital[i][j] = Integer.parseInt(st.nextToken());
if (hospital[i][j] == 2) {
viruses.add(new int[]{i, j});
} else if (hospital[i][j] == 0) {
blankCount++;
}
}
}
run(0, n * m, 0);
System.out.println(result);
}
private static void run(int start, int max, int count) {
if (count == 3) {
spread();
return;
}
int x, y;
for (int i = start; i < max; i++) {
x = i / m;
y = i % m;
if (hospital[x][y] == 0) {
hospital[x][y] = 1;
run(i + 1, max, count + 1);
hospital[x][y] = 0;
}
}
}
private static void spread() {
boolean[][] visited = new boolean[n][m];
Queue<int[]> queue = new ArrayDeque<>(viruses.size());
for (int[] virus : viruses) {
queue.add(virus);
visited[virus[0]][virus[1]] = true;
}
int nx, ny, countOfVirus = 0;
while (!queue.isEmpty()) {
int[] pos = queue.poll();
for (int i = 0; i < 4; i++) {
nx = pos[0] + dx[i];
ny = pos[1] + dy[i];
if (nx < 0 || nx > n - 1 || ny < 0 || ny > m - 1
|| visited[nx][ny] || hospital[nx][ny] == 1) {
continue;
}
countOfVirus++;
visited[nx][ny] = true;
queue.add(new int[]{nx, ny});
}
}
result = Math.max(result, blankCount - countOfVirus);
}
}
참고자료
- https://www.acmicpc.net/problem/14502
'Algorithm > BOJ' 카테고리의 다른 글
| [백준 - 1043] 거짓말 - Java (0) | 2022.03.30 |
|---|---|
| [백준 - 18111] 마인크래프트 - Java (0) | 2022.03.26 |
| [백준 - 11501] 주식 - Java (0) | 2022.03.16 |
| [백준 - 2512] 나이트 이동 - Java(Feat. DFS vs BFS) (0) | 2022.03.15 |
| [백준 - 2512] 예산 - Java (0) | 2022.03.08 |