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

치즈 성공출처분류

Gold IV 너비 우선 탐색깊이 우선 탐색그래프 이론그래프 탐색구현시뮬레이션 난이도 제공: solved.ac — 난이도 투표하러 가기

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	128 MB	8532	3840	2861	45.521%

문제

N×M (5≤N, M≤100)의 모눈종이 위에 아주 얇은 치즈가 <그림 1>과 같이 표시되어 있다. 단, N 은 세로 격자의 수이고, M 은 가로 격자의 수이다. 이 치즈는 냉동 보관을 해야만 하는데 실내온도에 내어놓으면 공기와 접촉하여 천천히 녹는다. 그런데 이러한 모눈종이 모양의 치즈에서 각 치즈 격자(작 은 정사각형 모양)의 4변 중에서 적어도 2변 이상이 실내온도의 공기와 접촉한 것은 정확히 한시간만에 녹아 없어져 버린다. 따라서 아래 <그림 1> 모양과 같은 치즈(회색으로 표시된 부분)라면 C로 표시된 모든 치즈 격자는 한 시간 후에 사라진다.

<그림 2>와 같이 치즈 내부에 있는 공간은 치즈 외부 공기와 접촉하지 않는 것으로 가정한다. 그러므 로 이 공간에 접촉한 치즈 격자는 녹지 않고 C로 표시된 치즈 격자만 사라진다. 그러나 한 시간 후, 이 공간으로 외부공기가 유입되면 <그림 3>에서와 같이 C로 표시된 치즈 격자들이 사라지게 된다.

모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다. 입력으로 주어진 치즈가 모두 녹아 없어지는데 걸리는 정확한 시간을 구하는 프로그램을 작성하시오.

입력

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

출력

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

예제 입력 1

xxxxxxxxxx
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

 

 

풀이

외부공기 / 내부공기를 나눠주면 쉽게 풀 수 있는 문제입니다.

 

xxxxxxxxxx
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
    static int map[][];
    static int n,m;
    static boolean visited[][];
    static int dx [] = {0,0,1,-1};
    static int dy [] = {1,-1,0,0};
    static ArrayList<Node>list = new ArrayList<>();
    public static void print() {
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                System.out.print(map[i][j]+" ");
            }
            System.out.println();
        }
    }
    public static void main(String[] args) throws  IOException {
    
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        
        String [] input = br.readLine().split(" ");
        
        n = Integer.parseInt(input[0]);
        m = Integer.parseInt(input[1]);
        
        map = new int[n][m];
        visited = new boolean[n][m];
        
        for(int i=0; i<n; i++) {
            input = br.readLine().split(" ");
            for(int j=0; j<m; j++) {
                map[i][j] = Integer.parseInt(input[j]);
            }
        }
        
        
        int ans = 0;
        while(true) {
    
    
            list.clear();
            if(gameOver()) {
                break;
            }
            
            
            // 1. 치즈 외부에 있는 공기 구하기
            bfs(0,0);
            
            // 2. 치즈중 외부치즈와 2면이상 맞닿은거 체크
            for(int i=0; i<n; i++) {
                for(int j=0; j<m; j++) {
                    if(map[i][j]==1 && check(i,j)) {
                        list.add(new Node(i,j));
                    }
                }
            }
            
            
            // 3. 녹아야 할 예정인 치즈 녹이기
            
            for(Node a: list) {
                map[a.x][a.y]= 0; 
            }
            
            
            // 4. 외부치즈들 다시 0으로 바꿔줌
            for(int i=0; i<n; i++) {
                for(int j=0; j<m; j++) {
                    if(map[i][j]==2) {
                        map[i][j]=0;
                    }
                }
            }
            ans++;
        }
        
        System.out.println(ans);
​
    }
    public static boolean check(int x, int y) {
        
        int cnt = 0;
        for(int i=0; i<4; i++) {
            int nx = x+dx[i];
            int ny = y+dy[i];
            
            if(isRange(nx,ny) && map[nx][ny]==2) {
                cnt++;
            }
        }
        
        if(cnt>=2) {
            return true;
        }
        else {
            return false;
        }
    }
    public static boolean isRange(int x, int y) {
        if(x>=0 && y>=0 && x<n && y<m) {
            return true;
        }
        return false;
    }
    public static void bfs(int x, int y) {
        Queue<Node> q = new LinkedList<>();
        visited = new boolean[n][m];
        q.add(new Node(x,y));
        visited[x][y] = true;
        map[x][y]= 2;
        while(!q.isEmpty()) {
            Node a = q.poll();
            
            for(int i=0; i<4; i++) {
                int nx = a.x+dx[i];
                int ny = a.y+dy[i];
                
                if(isRange(nx,ny) && !visited[nx][ny] && map[nx][ny]==0) {
                    q.add(new Node(nx,ny));
                    visited[nx][ny]=  true;
                    map[nx][ny] = 2;
                }
            }
        }
    }
    public static boolean gameOver() {
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                if(map[i][j]==1) {
                    return false;
                }
            }
        }
        return true;
    }
}
class Node{
    int x,y;
    Node(int x, int y){
        this.x=x;
        this.y=y;
    }
}
​