[BFS] 백준 2638번 치즈 - JAVA

 

요즘 싸피 우리반 친구들은 어떤 문제를 푸나 궁금해서

그룹에 들어가봤더니 '치즈' 문제를 많이 풀고 있어서 나도 도전했다!!!

 

10일 전에 푼 치즈 골드 4 문제

 

이 문제는 10일 전에 풀었던 2636번 골드 4 문제 치즈이다.

오늘 골드 3 치즈도 유사하게 문제를 풀었다.

다만, 2638번 치즈는 2변에 공기가 통해야지 녹는다는 조건이 하나 더 붙었기 때문에 유의해준다.

 

너무 오랜만에 봐서 설계 로딩 시간이 좀 길었던 문제다 ㅎㅎ...

집에와서 차분히 풀어보니 한 방에 클리어했던 문제!

 

렛츠 기릿!

 

 

---

1. 출처

---

2638번: 치즈

 

 

 

 

---

2. 설계

---

 

1) 전체 치즈 수를 구해주자.

// 초기화
map = new int[N][M]; 
        
for(int i=0;i<N;i++) {
	for(int j=0;j<M;j++) {
		map[i][j]=sc.nextInt();
		if(map[i][j]==1) totalCheeze++;
	}
}

치즈 현황을 받아주면서 치즈 갯수도 함께 세준다.

 

 

2) BFS 적용

 //bfs (총 치즈수가 0개가 될 때까지)
while(totalCheeze!=0) {
	visited = new int[N][M];
	cheeze(0,0);
	day++;        	
}

치즈 전체 수가 0이 될 때까지 BFS를 이용해 치즈를 녹여볼 것이다.

cheeze 함수에 BFS가 적용되어 있는데, 이 함수를 들어가면 하루하루 녹게 되는 치즈를 모두 녹이고 함수를 나오기 때문에 day를 1일 추가해준다.

 

그리고 가장 중요한 것은 항상 (0,0)의 시작점에서 시작한다는 점이다.

치즈가 존재하지 않는 공간 즉, 외부 공기가 나도는 곳을 큐에 넣어줄 것이기 때문이다.

 

가장 직관적인 예를 들기 위해 (3,0) 부분을 탐색한다 생각한다.

모든 분들이 문제를 풀 때 공기가 통하지 않을 저 가운데 부분이 고민스러웠을 것이다.

 

일단 '요기!'라고 써져있는 부분이 공기가 통하는 0인 지점이므로 큐에 들어있었을 것이고, 큐에서 나왔을 때 4방 탐색을 하며 치즈가 없는 0인 곳이며 방문하지 않은 지점은 모두 큐에 넣었을 것이다.

 

하지만 (3,1)은 치즈가 있는 부분이다. visited[3][1] ++만 해주고, 큐에 넣어주지 않는다.

큐에 넣어주지 않기 때문에 그 뒤인 (3,2) (3,3) (3,4) ... 등등은 자연스럽게 4방 탐색에서 벗어나기 때문에 치즈를 녹이지 않는다.

 

치즈가 있는 공간이자 visited가 2이상인 곳은 치즈가 녹았다고 판단하고 치즈를 녹여준다. map[row][col] = 0

public static void cheeze(int startR, int startC){
        int[][] drc = {{-1,0},{1,0},{0,-1},{0,1}};
    	Queue<Node> q = new LinkedList<>();
        
        q.add(new Node(startR,startC));
        visited[startR][startC] = 1;
        
        while(!q.isEmpty()) {
        	Node cur = q.poll();
        	
        	for(int d=0;d<4;d++) {
        		int row = cur.row+drc[d][0];
        		int col = cur.col+drc[d][1];
        		
        		if(row<0 || row>=N || col<0 || col>=M) continue;
        		if(map[row][col]==0 && visited[row][col]==0) {
        			q.add(new Node(row,col));
        			visited[row][col]++;
        		}
        		if(map[row][col]==1) {
        			visited[row][col]++;
        			//공기에 2변 이상 노출 -> 녹음
        			if(visited[row][col]>=2) {
        				map[row][col]=0;
        				totalCheeze--;
        			}
        		}
        	}//4방 탐색 끝
        }
    }

 

 

3) 몇 일이 걸렸는 지 출력해준다. 

//bfs (총 치즈수가 0개가 될 때까지)
while(totalCheeze!=0) {
	visited = new int[N][M];
	cheeze(0,0);
	day++;        	
}
        
System.out.println(day);

치즈 수가 0이 되면 걸린 일자를 출력해준다.

 

 

---

3. 전체 코드

---

package 백준2638;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class 치즈 {
    static int[][] map;
    static int[][] visited;
    static int day;
    static int totalCheeze;//전체 치즈수
    static int N,M;
    
    static class Node{
        int row;
        int col;
        public Node(int row, int col) {
            super();
            this.row = row;
            this.col = col;
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        N = sc.nextInt(); //세로 격자의 수
        M = sc.nextInt(); //가로 격자의 수
        
        // 초기화
        map = new int[N][M]; 
        
        for(int i=0;i<N;i++) {
            for(int j=0;j<M;j++) {
                map[i][j]=sc.nextInt();
                if(map[i][j]==1) totalCheeze++;
            }
        }
        
        // 입력 받기 끝
        
        //bfs (총 치즈수가 0개가 될 때까지)
        while(totalCheeze!=0) {
        	visited = new int[N][M];
        	cheeze(0,0);
        	day++;        	
        }
        
        System.out.println(day);

    }
    
    public static void cheeze(int startR, int startC){
        int[][] drc = {{-1,0},{1,0},{0,-1},{0,1}};
    	Queue<Node> q = new LinkedList<>();
        
        q.add(new Node(startR,startC));
        visited[startR][startC] = 1;
        
        while(!q.isEmpty()) {
        	Node cur = q.poll();
        	
        	for(int d=0;d<4;d++) {
        		int row = cur.row+drc[d][0];
        		int col = cur.col+drc[d][1];
        		
        		if(row<0 || row>=N || col<0 || col>=M) continue;
        		if(map[row][col]==0 && visited[row][col]==0) {
        			q.add(new Node(row,col));
        			visited[row][col]++;
        		}
        		if(map[row][col]==1) {
        			visited[row][col]++;
        			//공기에 2변 이상 노출 -> 녹음
        			if(visited[row][col]>=2) {
        				map[row][col]=0;
        				totalCheeze--;
        			}
        		}
        	}//4방 탐색 끝
        }
    }

}

 

---

꾸준히 1문제씩 1달이 지났다!!바쁜 싸피 일상 속에서 쉽든 어렵든 한 문제씩 풀어나갔던 지난 날들 너무 뿌듯하다 ㅎㅎ

 

화이팅!