2638_치즈

사용 알고리즘: bfs

사용 언어: java

 

package week34;

import java.util.*;
public class Main_bj_2638_치즈 {
	static int n, m, map[][], changed;
	static int[] dx = {-1,1,0,0};
	static int[] dy = {0,0,-1,1};

	public static void main(String[] args) {
		init_2638();
		
		int answer = 0;
		while(true) {
			changed = 0;
			
			//0(치즈)에서 사방탐색 후, 주변 -2의 개수 구하기
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					if(map[i][j] == 0) {
						findMinus2(i,j);
						if(map[i][j] >= 2) changed++;
					}
				}
			}
			//0이 어떻게 바뀌었나
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					//1이면, 다시 0으로 바꾸기
					if(map[i][j] == 1) map[i][j] = 0;
					
					//2이상이면, -2로 바꾸기+거기서 bfs돌려서 -2보다 작으면 -2로 바꾸기
					if(map[i][j] >= 2) {
						map[i][j] = -2;
						meltCheese(i, j);
					}
				}
			}
			 
			 
			if(changed == 0) break;
			answer++;
		}
		System.out.println(answer);
	}

	private static void meltCheese(int x, int y) {
		Queue<int[]> q = new ArrayDeque<>();
		q.add(new int[] {x, y});
		
		while(!q.isEmpty()) {
			int[] p = q.poll();
			
			for (int d = 0; d < 4; d++) {
				int nx = p[0] + dx[d];
				int ny = p[1] + dy[d];
				
				if(inMap(nx, ny) && map[nx][ny] < -2) {
					map[nx][ny] = -2;
					q.add(new int[] {nx, ny});
				}
			}
		}
	}

	private static void findMinus2(int x, int y) {
		for (int d = 0; d < 4; d++) {
			int nx = x + dx[d];
			int ny = y + dy[d];
			
			if(inMap(nx, ny) && map[nx][ny] == -2)
				map[x][y]++;
		}
	}

	private static void init_2638() {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		m = sc.nextInt();
		map = new int[n][m];
		for (int i = 0; i < map.length; i++) {
			Arrays.fill(map[i], -1);
		}
		
		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < m; j++) {
				if(sc.nextInt() == 1) 
					map[i][j] = 0;
			}
		}
		
		int hh = -2;
		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < m; j++) {
				if(map[i][j] == -1) {
					bfs_2638(i,j, hh);
					hh--;
				}
			}
		}
	}

	private static void bfs_2638(int sx, int sy, int hh) {
		Queue<int[]> q = new ArrayDeque<>();
		q.add(new int[] {sx, sy});
		map[sx][sy] = hh;
		
		while(!q.isEmpty()) {
			int[] p = q.poll();
			
			for (int d = 0; d < 4; d++) {
				int nx = p[0] + dx[d];
				int ny = p[1] + dy[d];
				
				if(inMap(nx, ny) && map[nx][ny] == -1) {
					map[nx][ny] = hh;
					q.add(new int[] {nx, ny});
				}
			}
		}
	}

	private static boolean inMap(int nx, int ny) {
		if(nx>=0&&nx<n && ny>=0&&ny<m) return true;
		return false;
	}

}

 

 

메모리를 효율적으로 사용하려고 노력 했다

visit 배열을 포함한 추가적인 배열을 만들지 않고, map[][]으로만 끝내려고 했다!!

 

 

1. 처음 map은 -1로 채우고, 치즈가 있는 부분만 0으로 바꿈

 

2. -1인 부분은 bfs를 돌면서, -2, -3… 등으로 바꿔치기(빈 곳의 덩어리 찾기)

   - 이 과정이 필요한 이유?? ⇒ 문제에서 알 수 있듯, “치즈 내부에 있는 공간은 치즈 외부 공기와 접촉하지 않는 것으로 가정한다.”

 

3. 0(치즈)에서, 사방 탐색 후, -2의 개수를 더한다 (이렇게 하면!)

 

4. 0이 어떻게 바뀌었나?

  - 1이면, 다시 0으로 바꾸기

  - 2이상이면(녹는 치즈), -2로 바꾸고, 이 위치를 시작으로 -2보다 작은 곳은 -2로 바꾸기

 

아쉬운 점?

bfs를 하나의 함수로 표현할 수 있지 않을까