[백준 2636] 치즈 -JAVA //le_effort

치즈

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	128 MB	6911	3215	2427	48.706%

문제

아래 <그림 1>과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(<그림 1>에서 네모 칸에 X친 부분)에는 치즈가 놓여 있지 않으며 치즈에는 하나 이상의 구멍이 있을 수 있다.

이 치즈를 공기 중에 놓으면 녹게 되는데 공기와 접촉된 칸은 한 시간이 지나면 녹아 없어진다. 치즈의 구멍 속에는 공기가 없지만 구멍을 둘러싼 치즈가 녹아서 구멍이 열리면 구멍 속으로 공기가 들어가게 된다. <그림 1>의 경우, 치즈의 구멍을 둘러싼 치즈는 녹지 않고 ‘c’로 표시된 부분만 한 시간 후에 녹아 없어져서 <그림 2>와 같이 된다.

다시 한 시간 후에는 <그림 2>에서 ‘c’로 표시된 부분이 녹아 없어져서 <그림 3>과 같이 된다.

<그림 3>은 원래 치즈의 두 시간 후 모양을 나타내고 있으며, 남은 조각들은 한 시간이 더 지나면 모두 녹아 없어진다. 그러므로 처음 치즈가 모두 녹아 없어지는 데는 세 시간이 걸린다. <그림 3>과 같이 치즈가 녹는 과정에서 여러 조각으로 나누어 질 수도 있다.

입력으로 사각형 모양의 판의 크기와 한 조각의 치즈가 판 위에 주어졌을 때, 공기 중에서 치즈가 모두 녹아 없어지는 데 걸리는 시간과 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 치즈가 없는 칸은 0, 치즈가 있는 칸은 1로 주어지며 각 숫자 사이에는 빈칸이 하나씩 있다.

출력

첫째 줄에는 치즈가 모두 녹아서 없어지는 데 걸리는 시간을 출력하고, 둘째 줄에는 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 출력한다.

예제 입력 1

xxxxxxxxxx
13 12
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 0 0 0
0 1 1 1 0 0 0 1 1 0 0 0
0 1 1 1 1 1 1 0 0 0 0 0
0 1 1 1 1 1 0 1 1 0 0 0
0 1 1 1 1 0 0 1 1 0 0 0
0 0 1 1 0 0 0 1 1 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0

예제 출력 1

xxxxxxxxxx
3
5

 

 

풀이

구역 나누기가 중요하다.

외부공기, 내부공기, 치즈 이렇게 총 3개의 구역을 나눌 수 있는데

외부공기는 -1로 설정 해줬다.

문제의 조건중 가장자리에는 치즈가 무조건 안 온다고 하였으니

0,0부터 dfs를 통해 외부 공기를 -1로 바꿔주었다

 

맵은 총 3가지 상태로 나타난다

-1 : 외부공기

1 : 치즈

0 : 내부공기

 

문제를 잘 읽어보면 왜 외부공기와 내부공기를 나눠야 하는지 알 수 있을 것이다.

내가 쓴 풀이의 진행방향

1. while(true)문으로 진행

    

2. map에 치즈가 하나도 없다면 종료

    

3. map에 치즈가 하나라도 있다

   3-1 dfs를 통해 외부공기를 얻어줌 (막혀있는 치즈가 뚫리면서 내부공기가 외부공기로 바뀔수 있으니 매번 진행 해줘야함)

    

   3-2 0,0~n,m 까지 2중반복문 탐색을 하며 가장자리의 치즈 인지 확인

   • 가장자리 치즈가 뭐야?

     '외부공기'와 맞닿은 치즈만 구멍속으로 공기가 들어가니까 외부공기와 맞닿은 치즈인지 확인 하는 것 내부 치즈는 아직 할 필요가 없다

    

   3-3 가장자리 치즈이면 큐에 넣어준다

 

4. 3번의 과정이 다 끝나면 큐에 들어있는 치즈를 외부공기인 -1로 바꿔줌

   왜?

   치즈가 녹아내렸으니까 공기로 바뀐다

   이 치즈는 '외부공기'와 맞닿아서 녹아버린 치즈니 내부공기가 아니라 외부공기로 바꿔준다

 

전체코드

import java.io.*;
import java.util.*;
public class Main {
    static int n,m;
    static int map[][];
    static int dx[] = {0,0,1,-1};
    static int dy[] = {1,-1,0,0};
    static boolean visited[][];
    static int time = 0;
    static int cheese;
    static boolean flag;
    static boolean dfs_visited[][];
    static Queue<Node> q = new LinkedList<>();
    static Queue<Node>air = new LinkedList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] t = br.readLine().split(" ");
        n = Integer.parseInt(t[0]);
        m = Integer.parseInt(t[1]);
        visited = new boolean[n][m];
        map = new int[n][m];
        for(int i=0; i<n; i++) {
            String[] tt = br.readLine().split(" ");
            for(int j=0; j<m; j++) {
                map[i][j]= Integer.parseInt(tt[j]);
            }
        }
        while(true) {
            flag = false;   
            for(int i=0; i<n; i++) {
                for(int j=0; j<m; j++) {
                    if(map[i][j]==1) {
                        flag = true;
                    }
                }
            }
            if(flag) {  // 치즈가 남아 있을 때
                visited = new boolean[n][m];
                time ++;
                cheese = get_cheese();
                dfs_visited = new boolean[n][m];
                dfs(0,0);   
                for(int i=0; i<n; i++) {
                    for(int j=0; j<m; j++) {
                        if(map[i][j]==1) {
                            for(int k=0; k<4; k++) {    // 현재 치즈의 4방향 중 한군대라도 공기가 있으면 녹일수 있으니 그걸 체크하는 과정
                                int nx = i+dx[k];
                                int ny = j+dy[k];
                                if(isRange(nx,ny) && map[nx][ny]==-1 && !visited[i][j]) {
                                    visited[i][j]=true;
                                    q.add(new Node(i,j));   //녹을 예정인 치즈를 큐에 담아준다.
                                }
                            }
                        }
                    }
                }
                while(!q.isEmpty()) {
                    Node a = q.poll();
                    map[a.x][a.y] = -1; // 치즈를 녹였다
                }
            }
            else {      // 치즈가 다 녹은것
                System.out.println(time);
                System.out.println(cheese);
                break;
            }
        }
    }
    public static int get_cheese() {
        int cnt =0;
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                if(map[i][j]==1) {
                    cnt++;
                }
            }
        }
        return cnt;
    }
    public static void dfs(int x, int y) {
        dfs_visited[x][y]=true;
        map[x][y]=-1;
        for(int i=0; i<4; i++) {
            int nx = x+dx[i];
            int ny = y+dy[i];
            if(isRange(nx,ny) && map[nx][ny]!=1 && !dfs_visited[nx][ny]) {
                dfs(nx,ny);
            }
        }
    }
    public static boolean isRange(int x, int y) {
        if(x>=0 && y>=0 && x<n && y<m) {
            return true;
        }
        return false;
    }
}
class Node{
    int x,y;
    Node(int x, int y){
        this.x=x;
        this.y=y;
    }
}