[백준] 2636번 치즈 JAVA (자바) 풀이

문제 2636(BFS)

 

 : 회색으로 표시된 부분 = 치즈

   X친 부분 = 판의 가장자리 (치즈 없음)

   ‘c’로 표시된 부분만 한 시간 후에 녹고 빈칸과 접촉하는 치즈는 c 표시 해준다

   단 치즈로 둘러쌓여있는 빈칸은 접촉해도 c표시 없어도 된다

 :  치즈가 모두 녹아 없어지는 데 걸리는 시간과 모두 녹기 한 시간 전에 남아있는 치즈조각 개수 구해라

 

 

[입력]

 :  첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수 (길이는 최대 100)

    판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지

    (치즈가 없는 칸은 0, 치즈가 있는 칸은 1) 

  

 

 [출력]

 :  첫째 줄에는 치즈가 모두 녹아서 없어지는 데 걸리는 시간을 출력

 :  둘째 줄에는 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 출력한다.

 

 

 [문제접근]

 

 1. 처음부터 치즈를 계산하기

• 그때그때 치즈 개수를 계산하면 모두 녹기 직전까지 계속해서 갱신해줘야 하는 번거로움
• 아예 처음부터 치즈 모두 계산 후 bfs 돌릴 때마다 차감하는 형식이 더 간편
  

 

 2. 빈칸이면 큐에 추가하고 치즈면 빈칸으로 보내기

• 빈칸이면 계속해서 나아가야 하기 때문에 별도의 지시는 없고 그냥 큐에만 추가
• 치즈라면 치즈를 녹여야 하므로 해당배열 0으로 변경 후 치즈 차감하기

 

3. time을 증가하는 기준이란

• 공기와 접촉하는 치즈란 빈칸과 접촉하는 치즈와 같다
• 즉 치즈 뭉텅이의 테두리를 제거하는데 1시간이 걸린다
• 핵심은 빈칸일 때만 큐에 추가한다는 것이다
  치즈는 큐에 추가하지 않아서 치즈 밖의 모든 빈칸들만 큐에 집어넣고 확인한다 
  치즈는 큐에 넣지 않아서 스스로 옆으로 이동할 수가 없다 
  즉 테두리를 제외한 안쪽 치즈들은 다음턴에 녹여야한다
  모든 확인이 끝났다면 bfs 종료
• 현지점이 공기 다음지점이 치즈여야 녹이기 가능

 

4. time은 bfs 후에 cheese는 bfs 전에

• time은 bfs를 진행한 후 모든 치즈가 녹을 경우의 수다
• 하지만 cheese는 모든 치즈가 녹기 전 바로 직전의 cheese가 필요하다
• while문을 통해 한시간에 녹을 수 있는 치즈를 계산하는게 bfs이므로 bfs 이전에 cheese를 먼저 저장한다

 

 

 [코드]

import java.io.*;
import java.util.*;
public class Main{
    static int N,M,arr[][],cheese;
    static int time=0;
    static boolean visit[][];
    static int dx[] = {0,0,1,-1};
    static int dy[] = {1,-1,0,0}; 
    static Queue<int[]> q = new LinkedList<>();
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new int[N][M];
        
        cheese =0;
        
        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<M; j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
                if(arr[i][j]==1){
                    cheese++;
                }
            }
        }
        
        int result = 0;
        while(cheese!=0){
            visit = new boolean[N][M];
            result = cheese;
            bfs();
            time++;
        }
        
        System.out.println(time);
        System.out.println(result);
        
    }
    
    static void bfs(){
        q.add(new int[]{0,0});
        visit[0][0] = true;
        while(!q.isEmpty()){
            int p[] = q.poll();
            
            for(int i=0;i<4;i++){
                int nx = p[0]+dx[i];
                int ny = p[1]+dy[i];
                if(0<=nx&&nx<N && 0<=ny&&ny<M && !visit[nx][ny]){
                    visit[nx][ny]=true;
                    
                    if(arr[nx][ny]==1){
                        arr[nx][ny] = 0;
                        cheese--;
                    }
                    else if(arr[nx][ny]==0){
                        q.add(new int[]{nx,ny});
                    }
                }
            }
        }
    }
}

 

 [해설]
     

 :  static int N,M,arr[][],cheese;
    static int time=0;  모든 bfs걸친 총 결과라서 전역변수로 초기화
    static boolean visit[][];
    static int dx[] = {0,0,1,-1};  상하좌우
    static int dy[] = {1,-1,0,0};  상하좌우
    static Queue<int[]> q = new LinkedList<>();  큐선언
   

 :  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    N = Integer.parseInt(st.nextToken());  행 인덱스
    M = Integer.parseInt(st.nextToken());  열 인덱스
    arr = new int[N][M];  치즈 배열판
        
 :  cheese =0;  치즈 초기화
    for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<M; j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
                if(arr[i][j]==1){  치즈 개수부터 먼저 세기
                    cheese++;
                }
            }
    }
        
 :  int result = 0;  치즈 몇 개 인 지 저장
    while(cheese!=0){  치즈가 없다면 다 녹인거라 종료
            visit = new boolean[N][M];  bfs마다 방문기록 초기화
            result = cheese;  bfs 이전에 치즈 개수 저장 (이전 턴의 치즈개수)
            bfs();  bfs 실행
            time++;  치즈 모두 다 녹인 후에 타임 카운트
    }
        
 :  System.out.println(time);  시간 출력
    System.out.println(result);  다 녹아 없어지기 바로 직전의 치즈 개수 출력
        
    
 :  static void bfs(){  
        q.add(new int[]{0,0});  공기부터 시작
        visit[0][0] = true;  방문처리
        while(!q.isEmpty()){
            int p[] = q.poll();  큐에서 뽑기
            
            for(int i=0;i<4;i++){  상하좌우 이동
                int nx = p[0]+dx[i];
                int ny = p[1]+dy[i];
                if(0<=nx&&nx<N && 0<=ny&&ny<M && !visit[nx][ny]){  범위 안이라면
                    visit[nx][ny]=true;  방문처리부터 하기
                    
                    if(arr[nx][ny]==1){  테두리 치즈발견 (큐에 넣지 않아서 4방향 이동불가)
                        arr[nx][ny] = 0;  녹아서 공기로 변경 
                        cheese--;  치즈 녹이기
                    }
                    else if(arr[nx][ny]==0){  공기라면 큐에 넣어서 계속해 이동
                        q.add(new int[]{nx,ny});  큐에 추가
                    }
                }
            }
        }
    }
  


 

 

이제 풀어보러 갈께요 :)

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *

 

https://www.acmicpc.net/problem/2636