Q. 14502 연구소
Q. 14502 연구소
문제 : boj.kr/14502
골드 4 난이도의 문제이다.
바이러스(2) 벽(1) 빈 공간(0)을 의미하는 격자형 그래프가 주어지고,
바이러스는 빈 공간이 있으면 확산된다는 조건이 있다.
이 때 벽을 세 개 세워서 바이러스의 확산을 최대한 막는 방법을 물어보는 문제이다.
처음 문제를 봤을 때 든 생각은 벽을 세울 수 있는 모든 경우의 수를 dfs로 구현한 뒤
벽을 3개 만들었을 경우, 바이러스를 확산시켜 빈 공간의 수를 계산하는 방식을 떠올렸다.
근데 막상 구현을 하다 보니 너무 복잡해지는 것 같아 생각을 바꿨다.
아래와 같은 방식으로 구현을 했다.
1. 빈 공간(0)을 리스트에 모두 저장한다.
2. 벽을 최대 3개 세울 수 있으므로 3중for문을 이용해 벽을 세울 수 있는 모든 경우의 수를 구한다.
3. 벽을 3개 세웠을 때마다 바이러스가 확산됬을 때의 빈 공간의 수를 구한다.
사실 N, M의 최대값이 8이라 가능한 풀이 방식이고,
이 문제의 분류 중 브루트포스 알고리즘이 있어서 떠올린 방식이다.
세로, 가로가 N, M으로 주어지므로 시간복잡도는 아래와 같다.
1. 그래프중 0인 리스트를 저장 - O(N * M)
2. 3중 for문을 통해 가능한 벽의 위치를 저장 - 최악의 경우O(N^3 * M^3)
3. 만약 벽을 3개 세운 경우 BFS를 이용해 바이러스 확산 시 남은 빈 공간의 수 계산
이 경우 위의 시간복잡도에 곱해줘야 함 - O(N * M)
따라서 약 O(N^4 * M^4)으로 최악의 경우 약 8^8 = 16777216번 계산을 하면 답을 구할 수 있고,
시간초과는 걱정하지 않아도 된다
이 문제는 강의를 듣기 전에 나만의 방식으로 풀어본 것 이고,
내가 생각해도 3중 for문은 비효율적이라고 생각해서(약 O(N^8)의 풀이) 강의를 들어보고
좀 더 개선할 방향이 있는지 생각해봐야겠다,
풀고난 뒤 for문에 M, N값을 잘못 넣어서 런타임 에러가 나서 삽질을 해서 좀 더 슬픈 문제였다..
내 풀이는 아래와 같다
import java.io.*;
import java.util.*;
public class Main {
static FastReader scan = new FastReader();
static StringBuilder sb = new StringBuilder();
static int N, M;
static int cnt = 0;
static int[][] graph;
static int[] dy = new int[] {0, 1, 0, -1};
static int[] dx = new int[] {1, 0, -1, 0};
static List<int[]> zeroList;
static void input() {
N = scan.nextInt();
M = scan.nextInt();
graph = new int[N][M];
zeroList = new ArrayList<>();
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
graph[i][j] = scan.nextInt();
if (graph[i][j] == 0) zeroList.add(new int[] {i, j});
}
}
}
static void bfs() {
boolean[][] visit = new boolean[N][M];
Queue<int[]> queue = new LinkedList<>();
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (graph[i][j] != 0){
visit[i][j] = true;
if (graph[i][j] == 2) queue.add(new int[] {i, j});
}
}
}
while (!queue.isEmpty()) {
int[] cur = queue.poll();
for (int i = 0; i < 4; i++) {
int ny = cur[0] + dy[i];
int nx = cur[1] + dx[i];
if (ny < 0 || nx < 0 || ny == N || nx == M) continue;
if (visit[ny][nx]) continue;
visit[ny][nx] = true;
queue.add(new int[]{ny, nx});
}
}
int blankCnt = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) if (graph[i][j] == 0 && !visit[i][j]) blankCnt++;
}
cnt = Math.max(blankCnt, cnt);
}
static void pro() {
for (int i = 0; i < zeroList.size() - 2; i++) {
int[] a = zeroList.get(i);
graph[a[0]][a[1]] = 1;
for (int j = i + 1; j < zeroList.size() - 1; j++) {
int[] b = zeroList.get(j);
graph[b[0]][b[1]] = 1;
for (int k = j + 1; k < zeroList.size(); k++) {
int[] c = zeroList.get(k);
graph[c[0]][c[1]] = 1;
bfs();
graph[c[0]][c[1]] = 0;
}
graph[b[0]][b[1]] = 0;
}
graph[a[0]][a[1]] = 0;
}
System.out.println(cnt);
}
public static void main(String[] args) {
input();
pro();
}
static class FastReader {
// BufferedReader의 빠른 속도,
// + Scanner의 타입별 입력값을 받는 기능을 혼합
// (자바 내부에 구현된 Scanner는 속도가 느림)
// 다른분의 코드를 참고한 코드
BufferedReader br;
StringTokenizer st;
public FastReader() {
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws FileNotFoundException {
br = new BufferedReader(new FileReader(new File(s)));
}
String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
long nextLong() {
return Long.parseLong(next());
}
double nextDouble() {
return Double.parseDouble(next());
}
String nextLine() {
String str = "";
try {
str = br.readLine();
} catch (IOException e) {
e.printStackTrace();
}
return str;
}
}
}