구현
백준 14502번을 Java를 이용해 풀어보았다.
문제 링크 첨부한다.
https://www.acmicpc.net/problem/14502
DFS
먼저 DFS 를 이용해서 세 개의 벽을 칠 수 있는 모든 경우를 탐색한다. 세 개의 벽을 세우는 경우는 여러 경우가 나올 것이다. 각 경우마다 바이러스가 퍼지고 난 후의 새로운 map 을 그려서 여전히 0을 유지하고 있는 칸의 수를 카운트해서 기존의 최대 안전 영역 값과 비교해서 더 크다면 갱신해줘야한다.
그렇다면 세 개의 벽을 세운 map 에 바이러스가 퍼진 후의 newMap 은 어떻게 구할 것인가?
BFS
바이러스를 퍼뜨리기 위해서는 BFS 를 이용한다. 먼저 막대 3개 세운 newMap 을 탐색하며 바이러스가 있는 좌표들을 Queue 에 넣어준다.
Queue 가 빌 때까지 좌표들을 뽑아주며 그 좌표들의 상하좌우를 탐색해서 빈 공간이면 또 Queue 에 좌푯값들을 추가해주며 바이러스가 퍼진 Spreaded Map 을 구해준다.
Spreaded Map 이 완성되면 여전히 0을 유지하고 있는 칸의 수를 카운트해서 최대 안전 영역값을 갱신해준다.
코드는 다음과 같다.
import java.io.*;
import java.util.*;
public class Main {
static int N,M;
static int[][] map;
static int max = 0;
static int[][] dir = {{-1,0}, {1,0}, {0,-1}, {0,1}};
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
M = sc.nextInt();
map = new int[N][M];
for(int i=0; i<N; i++)
for(int j=0; j<M; j++)
map[i][j] = sc.nextInt();
backtracking(0);
System.out.println(max);
}
static void backtracking(int cnt){
if(cnt==3){
int[][] tmp = new int[N][M];
for(int i=0; i<N; i++)
tmp[i] = map[i].clone();
bfs(tmp);
return;
}
for(int i=0; i<N; i++){
for(int j=0; j<M; j++){
if(map[i][j]==0){
map[i][j] = 1;
backtracking(cnt+1);
map[i][j] = 0;
}
}
}
}
static void bfs(int[][] newMap){
Queue<Pos> q = new LinkedList<>();
for(int i=0; i<N; i++)
for(int j=0; j<M; j++)
if(newMap[i][j]==2)
q.add(new Pos(i,j));
while(!q.isEmpty()){
Pos cur = q.poll();
for(int d=0; d<4; d++){
int nR = cur.r + dir[d][0];
int nC = cur.c + dir[d][1];
if(isInRange(nR,nC) && (newMap[nR][nC]==0)){
newMap[nR][nC] = 2;
q.add(new Pos(nR,nC));
}
}
}
int cnt = 0;
for(int[] row: newMap)
for(int e: row)
if(e==0) cnt++;
max = Math.max(cnt, max);
}
static boolean isInRange(int r, int c){ return r>=0 && r<N && c>=0 && c<M; }
static class Pos{
int r,c;
Pos(int r, int c){
this.r = r;
this.c = c;
}
}
}실수들
깊은 복사와 얕은 복사
이전에도 다른 문제를 풀며 이에 대해 공부하고 블로그에 글을 남긴 적이 있다. 근데 또 잊어먹고 개뻘짓을 30분 넘게 했다.
1차원 배열은 다음과 같이 깊은 복사가 가능하다.
int[] copy = src.clone();
copy 배열의 원소를 건드려도 src는 변하지 않는다.
이를 2차원 배열에도 똑같이 적용한다면 다음과 같다.
int[][] copy = src.clone();
이때 copy 배열의 원소를 건드리면 src도 !!!!!변한다!!!!!!
2차원 배열 깊은 복사
이중 for문을 이용하거나 row 하나씩, 즉 1차원 배열 하나씩 O.clone()을 때려줘야한다.
이제 실수하지 말자.....
백트래킹과 DFS 의 차이
어설프게 공부해서 여지껏 백트래킹과 DFS 가 똑같은 건 줄 알았다. 일단 이것부터 잘못됐는데 다른 사람들의 코드를 살펴보니 모두 DFS라고만 메소드명을 지어뒀길래 backtracking이라 지었던 나와의 차이가 뭔지 살펴봤다.
나는 cnt뿐만 아니라 row 와 col 값까지 parameter 로 넘겨주며 재귀를 사용하고 있었다. 일단 이렇게 작성하면 답도 틀린다.
어쨌든 백트래킹은 미리 가지치기 작업을 하는 것이고 DFS 는 무식하게 다 도는 것!
1시간이 넘게 또 고민하던 점이 있는데... 왜 나처럼 row와 col값을 넘겨주면 답이 틀리게 나오는가...? 를 고민했다.
졸라게 고민하다가 결국 머릿속으로 안 돌아가서 내가 임의로 좀 더 작은 input 을 직접 작성해서 debug를 해봤다. debug 를 하며 알게 된 점은 저렇게 row와 col값을 param 으로 넘겨주면 중간에 확인 안하고 그냥 넘어가버리는 좌표들이 있었다..!!!
내가 굳이 저 방법을 계속 고집했던 이유는 cnt만 넘겨주는 재귀를 사용할 경우 이미 탐색했던 경우를 반복해서 또 탐색해야 하는 경우가 있어서 그게 싫은 탓에 중복을 없애려 했던 것이었다. 근데 중복은 없앨 수 있었지만 아예 탐색이 안 되는 위치가 생겨버렸기에... 중복이 생기더라도 cnt만 넘겨주는 DFS를 사용해야했다..!!!
한국말로 옮겨놓으니 아마 나밖에 못 알아 먹을 것 같지만(며칠 지나서 보면 나도 못 알아 먹을 것 같지만) 어쨌든 이러하다...
정말 아직 한참 부족하다...ㅠ
