[자바] 백준 2636 치즈

치즈가 녹는 시간을 구하는 문제입니다.

 

제가 치즈를 그렇게 좋아하는 편이 아니라, 문제에 몰입이 어려웠습니다. (피자는 좋아함)

 

만약 베스킨라벤스 아이스크림이 녹는 시간을 구하는 것이었다면, 좀 더 열중해서 풀었을 텐데

 

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

2636번: 치즈

 

 

어디서 많이 본 문제입니다. 뭘,, 녹이고 난리 치는 문제..

 

바로 백조의 호수 내 블로그 PPL 하기. 

https://hardworking-sloth.tistory.com/3

3917 백조의 호수

 

여기서 후드려 맞은 덕분에 쉽게 해결 방법을 생각할 수 있었습니다, 

 

- 문제 요약 

'치즈가 모두 녹는 시간과 녹기 바로 전 남아있는 치즈의 수를 구해라' 

 

- 조건

 공기에 닿아있는 치즈는 녹음

 치즈 안에 있는 공기는 치즈를 녹이지 못하지만, 밖 공기랑 만나는 순간 녹일 수 있음 

 

- N <= 100, 1초 

 

- 풀이 

 

N이 100이니 정말 하고 편-안 합니다. O(n^3)도 비벼볼 만해

 

그래도 한 번의 탐색을 통해서 문제를 해결하고 싶긴 했습니다.(같은 좌표는 한 번만 방문)

 

이렇게 뭘 녹이는 문제에서는 백조에서 해온 것처럼 '따블 que'를 생각하면 됩니다. 

 

공기를 탐색하면서 처음 만나는 치즈를 다른 큐에 넣어주고, 다시 다른 큐를 순회하면서 만나는 치즈를 다른 큐에 넣어주고.. 양쪽 큐가 빌 때까지 반복하면 됩니다. 

 

아 그리고 모두 녹기 전 치즈의 사이즈는 큐의 사이즈로 구해놓으면 되겠죠? 

 

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

public class Main {
    static int[][] map;
    static int[] dx={0,0,1,-1} , dy ={1,-1,0,0};
    private static class Node{
        int h;
        int w;
        Node(int h, int w){
            this.h = h;
            this.w = w;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        int h = Integer.parseInt(st.nextToken());
        int w= Integer.parseInt(st.nextToken());
        map = new int[h][w];
        for(int i=0;i<h;i++){
            st = new StringTokenizer(bf.readLine());
            for(int j=0;j<w;j++){
                int value = Integer.parseInt(st.nextToken());
                map[i][j] = value;
                // 치즈의 갯수가 필요한가..놉
            }
        }
        BFS(h, w);
    }
    public static void BFS(int h, int w){
        Queue<Node> q1 = new LinkedList<>();
        Queue<Node> q2 = new LinkedList<>();
        boolean[][] vist = new boolean[h][w];
        q1.add(new Node(0,0));
        vist[0][0] = true;
        int count = 0;
        int time = 0;
        while(!q1.isEmpty() || !q2.isEmpty()){
            while(!q1.isEmpty()){
                Node now = q1.poll();
                //vist
                for(int i=0;i<4;i++){
                    int nxtH = now.h+dx[i];
                    int nxtW = now.w+dy[i];
                    if(nxtH<h && nxtH>=0 && nxtW<w && nxtW>=0){
                        if(!vist[nxtH][nxtW]){
                            if(map[nxtH][nxtW]==1){
                                count++;
                                vist[nxtH][nxtW] = true;
                                q2.add(new Node(nxtH,nxtW));
                            }else{
                                vist[nxtH][nxtW] = true;
                                q1.add(new Node(nxtH,nxtW));
                            }
                        }
                    }
                }
            }
            time++;
            if(q2.isEmpty()){
                break;
            }
            count=q2.size();
            while (!q2.isEmpty()){
                Node now = q2.poll();
                //vist
                for(int i=0;i<4;i++){
                    int nxtH = now.h+dx[i];
                    int nxtW = now.w+dy[i];
                    if(nxtH<h && nxtH>=0 && nxtW<w && nxtW>=0){
                        if(!vist[nxtH][nxtW]){
                            if(map[nxtH][nxtW]==1){
                                count++;
                                vist[nxtH][nxtW] = true;
                                q1.add(new Node(nxtH,nxtW));
                            }else{
                                vist[nxtH][nxtW] = true;
                                q2.add(new Node(nxtH,nxtW));
                            }
                        }
                    }
                }
            }
            time++;
            if(q1.isEmpty()){
                break;
            }
            count= q1.size();
        }
        System.out.println(time-1);
        System.out.println(count);
    }
}

 

후기

1. 백조야 그때는 증오했지만 지금은 고맙구나

2. 다음번에는 아이수크림을 녹여주세요