문제 설명
문제 링크는 여기.
N*M 공간에 바이러스가 퍼지고 있다. 바이러스는 사방으로 증식하며, 벽은 넘을 수 없다.
우리는 3개의 벽을 세워 최대한 바이러스가 퍼지는 것을 방지해야 한다. 이때 3개의 벽을 세우는 것은 필수이다. 가장 최적의 위치에 벽을 세웠을 때, 확보할 수 있는 청정 구역의 개수를 구하자.
입력에서 바이러스는 2, 벽은 1, 청정 구역은 0으로 주어진다.
접근
BFS와 완전탐색 방법으로 풀어보았다.
먼저 입력을 받을 때 청정구역의 수를 센다. 이때 청정구역 중 3곳에 무조건 벽을 세울 것이므로 해당 값에 -3을 해준다.
순열을 통해 청정구역에 벽을 총 3개 세우고, 각 경우마다 bfs를 통해 감염된 구역의 개수를 구한다. 이때 감염된 구역 최소 개수를 저장한다.
이후 청정구역의 수에서 감염 구역 최소 개수를 빼면 최종적으로 남은 최대 청정구역의 수를 구할 수 있다.
먼저 입력을 받고 각각의 데이터를 저장한다.
이때 초기 바이러스 위치는 편의상 저장하여 활용하였다.
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
// 청정구역에 벽 3개 세울 것이므로 -3 미리 해둠
int safe = -3;
// 배열 범위 판단 로직 빼기 위해서 가장자리에 벽을 세움
int[][] arr = new int[N+2][M+2];
int size = 0;
int[][] virus = new int[N*M][];
// 배열 범위 판단 로직 빼기 위해서 가장자리에 벽을 세움
for(int n=0; n<N+2; n++)
for(int m=0; m<M+2; m++)
arr[n][m] = 1;
for(int n=0; n<N; n++) {
st = new StringTokenizer(br.readLine());
for(int m=0; m<M; m++) {
arr[n+1][m+1] = Integer.parseInt(st.nextToken());
// 바이러스 초기 위치면 저장
if(arr[n+1][m+1]==2)
virus[size++] = new int[] {n+1, m+1};
// 청정구역이면 safe + 1
else if(arr[n+1][m+1]==0) safe++;
}
}
// 청정구역 수 - 감염구역 최소 개수
System.out.println(safe - perm(0, arr, N, M, virus));완전 탐색은 순열 형태로 만들었다.
public static int perm(int idx, int[][] arr, int N, int M, int[][] virus) {
if(idx==3) return bfs(arr, virus);
int result = Integer.MAX_VALUE;
for(int n=0; n<N; n++) {
for(int m=0; m<M; m++) {
if(arr[n+1][m+1]!=0) continue;
int[][] copy = new int[N+2][M+2];
for(int i=0; i<N+2; i++) {
System.arraycopy(arr[i], 0, copy[i], 0, M+2);
}
copy[n+1][m+1] = 1;
result = Math.min(result, perm(idx+1, copy, N, M, virus));
}
}
return result;
}소스코드
최종적으로 제출한 코드는 다음과 같다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static int[] dr = {1, 0, -1, 0};
public static int[] dc = {0, -1, 0, 1};
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int safe = -3;
int[][] arr = new int[N+2][M+2];
int size = 0;
int[][] virus = new int[N*M][];
for(int n=0; n<N+2; n++)
for(int m=0; m<M+2; m++)
arr[n][m] = 1;
for(int n=0; n<N; n++) {
st = new StringTokenizer(br.readLine());
for(int m=0; m<M; m++) {
arr[n+1][m+1] = Integer.parseInt(st.nextToken());
if(arr[n+1][m+1]==2)
virus[size++] = new int[] {n+1, m+1};
else if(arr[n+1][m+1]==0) safe++;
}
}
System.out.println(safe - perm(0, arr, N, M, virus));
}
public static int perm(int idx, int[][] arr, int N, int M, int[][] virus) {
if(idx==3) return bfs(arr, virus);
int result = Integer.MAX_VALUE;
for(int n=0; n<N; n++) {
for(int m=0; m<M; m++) {
if(arr[n+1][m+1]!=0) continue;
int[][] copy = new int[N+2][M+2];
for(int i=0; i<N+2; i++) {
System.arraycopy(arr[i], 0, copy[i], 0, M+2);
}
copy[n+1][m+1] = 1;
result = Math.min(result, perm(idx+1, copy, N, M, virus));
}
}
return result;
}
private static int bfs(int[][] arr, int[][] virus) {
Queue<int[]> queue = new LinkedList<int[]>();
for(int i=0; true; i++) {
if(virus[i]==null) break;
queue.add(virus[i]);
}
int infection = 0;
while(!queue.isEmpty()) {
int[] v = queue.poll();
for(int i=0; i<4; i++) {
int r = v[0] + dr[i];
int c = v[1] + dc[i];
if(arr[r][c]==0) {
arr[r][c] = 2;
infection++;
queue.add(new int[] {r, c});
}
}
}
return infection;
}
}결과
제출 결과는 다음과 같다.
고찰
나는 평소 문제를 풀 때 꼭 인자로 나눠야하는 경우를 제외하면 전역변수로 선언해 사용한다. 하지만 이번엔 전역변수 사용을 지양해보았다.
알고리즘을 조금 하는 분에게 조언을 구했었는데, 함수 내 전역변수 사용을 지양하는 것이 좋다고 했다(특히 구현문제). 전역함수를 사용하게 되면 특히 디버깅에서 어려움이 생길 수 있기 때문이라고 한다. 다른 곳에서 해당 값을 임의로 변경할 수 있으므로 생각하는 결과가 나오지 않았을 때 함수 밖까지 모두 고려해 디버깅을 해야한다고..사실 더 자세히 말해줬는데 약간 졸려서 다 기억나지 않는다.
함수는 같은 인자를 주었을 때 같은 결과값을 반환하는 것이 가장 이상적이라고 해서 오늘은 한 번 필요한 값들을 모두 인자로 줘보았다. 그런데 초기 입력 받은 이후 상수로 활용되는 것도 인자로 준 것들이 있어서 다음 번에는 적절하게 섞어서 구현해보고자 한다.
