[백준] 2638 치즈 (Java)

백준 2638 치즈

문제

---

n*m 크기의 맵에 치즈는 1, 공기는 0으로 주어진다.
공기는 치즈로 둘러 싸여 외부와 접촉할 수 없는 내부 공기와 외부 공기로 나뉜다.
4변 중 적어도 2변 이상이 외부 공기와 접촉해 있는 치즈는 한시간 안에 녹아 없어진다고 할 때, 맵에 있는 치즈가 모두 녹아 없어지는 데 걸리는 시간을 구해야 한다.

입력

---

첫째 줄에는 모눈 종이의 크기를 나타내는 두 개의 정수 N, M(5<=N, M<=100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은
0으로 표시된다.

출력

---

주어진 치즈가 모두 녹아 없어지는데 걸리는 정확한 시간을 정수로 첫 줄에 출력한다.

예제 입력 1

---

8 9
0 0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0 0
0 0 0 1 1 0 1 1 0
0 0 1 1 1 1 1 1 0
0 0 1 1 1 1 1 0 0
0 0 1 1 0 1 1 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0

예제 출력 1

---

4

풀이

---

처음엔 치즈가 아닌 (값이 0인) 모든 좌표에서 BFS를 수행해 1로 둘러싸여 외부로 나갈 수 없으면(맵의 경계인 0, n, m에 도달하지 않고 BFS를 온전히 다 수행했으면) 해당 좌표의 값을 2로 변경해주었다. 그럼 0, 1, 2로 이루어진 맵이 구해지고, 이제 진짜 0과 두 방향 이상 접해있는 치즈를 녹이는 방식으로 구현했다. 하지만 모든 좌표마다 BFS를 수행해야 하기 때문에 메모리 초과가 났다.
하지만 이 문제는 간단하게 ,, 풀리는 문제였는데 ,,
내가 놓친 조건은 문제에 있는 '모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다.' 라는 문장이다 ,,
(0, 0)에서 시작해 BFS로 맵을 탐색해 가기 시작하면 치즈로 둘러싸인 내부 공기는 애초에 탐색 대상이 안된다 ,, visited 배열을 int 배열로 생성해 두번 이상 방문되면 치즈를 녹이면 됨 !

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int n, m;					// 모눈 종이 크기
    static int[][] map;					// 모눈 종이 정보
    static int[][] visited;				// 몇 번 방문했는지 체크하기 위해 int 배열 선언
    static int[] dr = {-1, 1, 0, 0};	// 상하좌우
    static int[] dc = {0, 0, -1, 1};	
    static int times =0;				// 걸리는 시간, 정답
    static class Node{
        int r;
        int c;
        public Node(int r, int c) {
            super();
            this.r = r;
            this.c = c;
        }
    }
    static void bfs() {
    	Queue<Node> q = new ArrayDeque<>();
    	// 문제 조건에서 가장자리는 치즈가 놓이지 않기 때문에
    	// (0, 0)부터 BFS를 시작하면 내부 공기는 신경쓰지 않아도 됨
    	q.add(new Node(0, 0));			

        while(!q.isEmpty()) {
            Node now = q.poll();
            
            // 상하좌우 탐색
            for(int d=0; d<4; d++) {
                int nr = now.r + dr[d];
                int nc = now.c + dc[d];
                if(nr<0 || nr>=n || nc<0 || nc>=m) continue;
                if(visited[nr][nc]==0&&map[nr][nc]==0) {
                    q.add(new Node(nr, nc));
                    visited[nr][nc] = 1;
                }
                // 치즈면
                if(map[nr][nc]==1) {
                	// nr, nc 좌표에 해당하는 값이 1이라는 것은 치즈와 인접했다는 것이기 때문에
                	// 몇 번 방문했는지를 체크하면 치즈가 녹을 자격이 있는 지 판단할 수 있음
                	visited[nr][nc] ++;
                	// 두 번이상 방문하면, 두 방향 이상 공기와 닿아있으면
                	if(visited[nr][nc]>=2) {
                		map[nr][nc] =0;	// 녹아버렷
                	}
                }
            }
        }
    }

    public static void main(String[] args) throws IOException, NumberFormatException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        map = new int[n][m];

        for(int i=0; i<n; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<m; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 치즈가 남아있나용 ?
        boolean isCheese = true;
        // 남아있으면 
        while(isCheese) {
        	visited = new int[n][m];
        	// 녹이세요
        	bfs();
        	
        	isCheese = false;
        	// 다 돌아도 치즈가 없으면 그만하고 times 출력 !
        	out:
        	for(int i=0; i<n; i++) {
        		for(int j=0; j<m; j++) {
        			if(map[i][j]!=0) {
        				isCheese = true;
        				break out;
        			}
        		}
        	}
        	times ++;
        }
        System.out.println(times);
    }
}