유사한 BFS문제를 2개 풀면서 익숙하게 만들었다. BOJ의 토마토와 연구소2를 풀었다. 유사한 문제를 풀면서 더욱 꼼꼼히 공부할 수 있었다.
(토마토)
import java.util.*;
import java.io.*;
public class Main {
public static int[][] box;
public static int[] dx = {0, 0, -1, 1};
public static int[] dy = {-1, 1, 0, 0};
public static int N, M;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] line = br.readLine().split(" ");
N = Integer.parseInt(line[1]);
M = Integer.parseInt(line[0]);
box = new int[N][M];
for(int i=0; i<N; i++){
line = br.readLine().split(" ");
for(int j=0; j<M; j++){
box[i][j] = Integer.parseInt(line[j]);
}
}
// 하루가 지나면 익는다!
// 1:익은토마토
// 0:익지않은
// -1: empty!
// 유의: 저쪽에서 익어오는 거, 이쪽에서 익어오는 거.. 동시에 고려해야 함
int[][] visit = new int[N][M];
Queue<int[]> q = new LinkedList<>();
// 익은 토마토 공평하게 먼저 q에 넣어두기 (거기서부터 공평히 익어가야 하니까)
for(int i=0; i<N; i++){
for(int j=0; j<M; j++){
if(box[i][j] == 1){
q.add(new int[]{i, j});
}
}
}
// 위에서 익토를 q에 넣어줬으니, poll만 해서 진행하면 된다. (익토 최소 1개 존재)
while(!q.isEmpty()){
int[] now = q.poll();
for(int k=0; k<4; k++){
int x = now[1] + dx[k];
int y = now[0] + dy[k];
if(x<0||y<0||y>=N||x>=M)
continue;
if(box[y][x]==0 && visit[y][x]==0){
visit[y][x] = visit[now[0]][now[1]] + 1; // 하루하루..
box[y][x] = 1; // 익었다..
q.add(new int[]{y, x});
}
}
}
// visit에서 가장 큰 값이, 모두 익을 때 까지의 최소 날짜다.
int res = 0;
int tmp = 0;
for(int i=0; i<N; i++){
for(int j=0; j<M; j++){
if((tmp = visit[i][j]) > res){
res = tmp;
}
}
}
if(!isPossible(box)){
res = -1;
}
System.out.println(res);
}
public static boolean isPossible(int[][] box){
for(int i=0; i<N; i++){
for(int j=0; j<M; j++){
if(box[i][j] == 0){
return false;
}
}
}
return true;
}
}
(연구소2)
import java.util.*;
import java.io.*;
public class Main {
public static int[][] map;
public static int[] dx = {0, 0, -1, 1};
public static int[] dy = {-1, 1, 0, 0};
public static int N, M;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] line = br.readLine().split(" ");
N = Integer.parseInt(line[0]); // 연구소 크기
M = Integer.parseInt(line[1]); // 놓을 바이러스 개수
// 0: 빈칸
// 1: 벽
// 2: 바이러스를 놓을 수 있는 곳
// 맵 구성 & 바이러스 놓을 후보지 candi 준비!
map = new int[N][N];
List<int[]> candi = new ArrayList<>();
for(int i=0; i<N; i++){
line = br.readLine().split(" ");
for(int j=0; j<N; j++){
map[i][j] = Integer.parseInt(line[j]);
if(map[i][j] == 2){
candi.add(new int[]{i, j});
}
}
}
// 바이러스 놓을 M조합 구하기
// - 헉 가변 M조합이라 반복문으로 구현이 난감하네
// - 백트래킹을 사용하자!
Map<Integer, Boolean> visited = new HashMap<>();
for(int i=0; i<candi.size(); i++){
visited.put(i, false);
}
List<int[]> output = new ArrayList<>();
combination(candi, visited, 0, candi.size(), M, output);
List<Integer> results = new ArrayList<>();
// 조합대로 바이러스 놓고 BFS 해보자.
// 최소시간인 조합 경우가 result 상황이다.
for(int i=0; i<output.size(); i+=M){
// map_에 map 복사
int[][] map_ = new int[N][N];
for(int a=0; a<N; a++){
for(int b=0; b<N; b++){
map_[a][b] = map[a][b];
}
}
List<int[]> virus3 = output.subList(i, i+M);
for(int[] point : virus3){
map_[point[0]][point[1]] = -1; // 바이러스는 -1이다.
}
// 2와 0은 공간
// 1은 벽
int day = BFS(map_);
// 결과값 계산하기 (퍼지는 최종 시간은? => 가장큰요소값임)
results.add(day);
}
int min = Integer.MAX_VALUE;
boolean flag = false;
for(int num : results){
if(num != -1){
flag = true;
if(num < min){
min = num;
}
}
}
if(flag)
System.out.println(min);
else
System.out.println(-1);
}
public static boolean emptySpace(int[][] map){
for(int i=0; i<N; i++){
for(int j=0; j<N; j++){
if(map[i][j] == 0)
return true;
}
}
return false;
}
public static int BFS(int[][] map){
Queue<int[]> q = new LinkedList<>();
int[][] visited = new int[N][N];
int[][] origin = new int[N][N];
// 바이러스 인 거 먼저 q에 넣기
for(int i=0; i<N; i++){
for(int j=0; j<N; j++){
origin[i][j] = map[i][j];
if(map[i][j] == -1){
q.add(new int[]{i, j});
}
visited[i][j] = 0;
}
}
int day = 0;
// 바이러스들 동시에 퍼지기 시작
for(int i=0; i<N; i++){
for(int j=0; j<N; j++){
while(!q.isEmpty()){
int[] point = q.poll();
for(int k=0; k<4; k++){
int x = point[1] + dx[k];
int y = point[0] + dy[k];
if(x<0||y<0||x>=N||y>=N)
continue;
if(map[y][x]==2||map[y][x]==0){
if(visited[y][x] == 0){
q.add(new int[]{y, x});
day = visited[point[0]][point[1]] + 1;
visited[y][x] = day; // 날짜(:=공간)
map[y][x] = -1;
}
}
}
}
}
}
// visited에서 가장 큰 값이 최종소요일이다.
// visitied에서 기존 벽을 세워보자.
for(int i=0; i<N; i++){
for(int j=0; j<N; j++){
if(origin[i][j]==-1) // visited에 바이러스 있던 곳 반영
visited[i][j] = -1;
if(origin[i][j]==1) // visited에 벽 반영
visited[i][j] = -9;
}
}
int res = 0;
for(int[] nums : visited){
for(int num : nums){
if(num == 0){
return -1; // 바이러스 안퍼진 곳, 즉 0이 있으면 바로 -1 때리기
}
if(num > res){
res = num;
}
}
}
return res;
}
public static void combination(List<int[]> arr, Map<Integer, Boolean> visited, int start, int n, int r, List<int[]> output){
if(r == 0){
for(int i=0; i<n; i++){
if(visited.get(i))
output.add(arr.get(i));
}
}
for(int i=start; i<n; i++){
visited.put(i, true);
combination(arr, visited, i+1, n, r-1, output);
visited.put(i, false);
}
}
}
반응형
