[백준] 알고리즘 분류(구현,JAVA)2636번, 치즈

문제 링크

2636번: 치즈

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 1시간마다 치즈는 공기에 접촉되면 녹습니다.

2. 치즈가 모두 녹는 시간과 모두 녹기 1시간 전에 치즈 개수를 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 치즈 녹는 시뮬레이션 진행합니다.

 

3. 시뮬레이션에 따른 결과를 출력합니다.

 

 

치즈 녹는 시뮬레이션.

 

치즈가 녹으려면 외부 공기를 만나야합니다.

 

1. 외부 공기에 대하여 BFS탐색을 진행하여 외부 공기와 만나는 치즈를 선별합니다.

 

※ (0, 0)은 항상 외부 공기입니다.

 

2. 외부 공기와 만난 치즈의 개수와 사각형 판에 대하여 치즈 녹기가 진행됩니다.

 

3. 치즈 녹은 결과에 따라

 

3-1) 치즈 다 녹았을 때 : 시뮬레이션 종료!

 

3-2) 치즈 다 녹지 않았을 때 : 1) 시뮬레이션 다시 진행

 

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

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

 

2. 치즈 녹는 시뮬레이션 진행합니다.

 

치즈가 녹는 시뮬레이션은 문제에서 그림으로 설명하고 있기 때문에 넘어가도록 하겠습니다.

 

3. 시뮬레이션에 따른 결과를 출력합니다.

 

모두 녹은 시간 : 3시간

 

모두 녹기 1시간 전 치즈 개수 : 5개(2시간)

 

3 5을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer을 이용하여 사각판 관련 띄어쓰기 기준 나누었습니다.
• 처음에 치즈가 존재한다면 시뮬레이션을 진행합니다.
• 시뮬레이션에 따른 결과를 BufferedWriter에 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• bfs함수는 (0, 0)을 기준으로 외부 공기와 만나는 치즈를 확인 및 녹는 과정을 진행합니다.
• inSpace함수는 사각판 안에 존재하는 좌표인지 확인합니다.

 

결과코드

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main{
    //사각형 판 위치 관련 클래스
    static class position{
        int x, y;	//x : x좌표, y : y좌표
        //생성자
        public position(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
    static int[][] map;		//사각형 판에 대한 배열
    static int[] dx = {0, 0, -1, 1};	//상하좌우 x변경값
    static int[] dy = {-1, 1, 0, 0};	//상하좌우 y변경값
    static int N,M;
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][M];
        int cheese = 0;	//현재 치즈의 개수
        //사각형 판에 대한 정보 저장
        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine()," ");
            for(int j=0;j<M;j++){
                map[i][j] = Integer.parseInt(st.nextToken());
                if(map[i][j] == 1)	//치즈일 때
                    cheese++;
            }
        }
        //처음부터 치즈가 없을 때
        if(cheese == 0)
            bw.write("0\n0");
        else{
            int time = 0;	//지나간 시간
            //시뮬레이션 진행
            while(true){
                time++;	//1시간 지나기!
                int removeCheese = bfs();	//외부 공기와 만나는 치즈 BFS 탐색
                if(cheese == removeCheese)	//현재 모든 치즈가 다 녹을 때
                    break;
                cheese -= removeCheese;	//치즈 녹기!
            }
            //지나간 시간과 1시간전 치즈 개수 BufferedWriter 저장
            bw.write(time + "\n" + cheese);
        }
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //외부 공기와 만나는 치즈를 찾기위해 BFS탐색하는 함수
    static int bfs(){
        boolean[][] visited = new boolean[N][M];	//방문 확인 배열
        Queue<position> queue = new LinkedList<>();	//BFS에 사용할 Queue
        Queue<position> hole = new LinkedList<>();	//외부 공기와 만나는 치즈 저장 Queue
        //(0, 0)은 항상 외부 공기! (0, 0)부터 탐색진행!
        queue.add(new position(0, 0));
        visited[0][0] = true;	//(0, 0) 방문 확인
        //탐색 진행
        while(!queue.isEmpty()){
            position cur = queue.poll();
            //좌표 이동
            for(int i=0;i<4;i++){
                int tempX = cur.x + dx[i];
                int tempY = cur.y + dy[i];
                if(inSpace(tempX,tempY) && !visited[tempY][tempX]){
                    visited[tempY][tempX] = true;
                    if(map[tempY][tempX] == 1) {	//외부 공기와 만나는 치즈일 때
                        hole.add(new position(tempX, tempY));
                    }else	//외부 공기일 때
                        queue.add(new position(tempX, tempY));
                }
            }
        }
        //외부 공기와 만난 치즈들 녹기 진행!
        for(position cur : hole) {
            map[cur.y][cur.x] = 0;
        }
        return hole.size();	//녹은 치즈 개수 반환
    }
    //BFS탐색으로 좌표 이동시 사각형 판에 존재하는 좌표인지 확인하는 함수
    static boolean inSpace(int x, int y){
        if(x >= 0 && y >= 0 && x < M && y < N)
            return true;
        return false;
    }
}