[BOJ] 2636.치즈(BFS, DFS).java

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

완전 탐색이 적용된 시뮬레이션 문제같다.

시뮬레이션은 뭐랏?! 조건을 잘 확인해주고 동작을 생각해보아야 한다!

* 공기와 접촉된 칸은 한 시간이 지나면 녹아 없어진다

* 치즈의 구멍 속에는 공기가 없지만 구멍을 둘러싼 치즈가 녹아서 구멍이 열리면 구멍 속으로 공기가 들어가게 된다

1. 치즈가 모두 없어질 때까지 동작은 반복

2. 공기를 bfs로 완전탐색하면서 치즈와 닿으면 녹여준다.

3. 치즈가 모두 녹아 없어지는 데 걸리는 시간과 모두 녹기 한 시간 전에 남아있는 치즈 칸의 개수를 저장

#. Code

시간복잡도는 O(time * N^2)으로 약 O(N^3)이 된다.

최대 N이 100일 경우 50 * 100 * 100 = 500,000 이므로

완전탐색으로 충분히 해결할 수 있다.

놓쳤던 부분은,

- (0,0)은 무조건 공기라는 것 ! 가장자리는 치즈가 놓여 있지 않는다고 했다..

- 전체 치즈 칸의 개수를 구한 후 줄여가면 더 좋은데, 매 time마다 치즈 칸을 count 했다..

import java.awt.Point;
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 BOJ2636 {
 
    static int R, C, map[][], time, res, total;
    static int[] dx = {-1, 0, 1, 0}, dy = {0, -1, 0, 1};
    
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        map = new int[R][C];
        
        for (int i = 0; i < R; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < C; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                // 초기 치즈 칸을 count
                if(map[i][j] == 1) total++;
            }
        }
        
        go();
        System.out.println(time + "\n" + res);
    }
 
    private static void go() {
 
        res = total;
        // 치즈가 모두 없어질 때까지 반복
        while(total != 0) {
            ++time;
            
            // 공기가 퍼지면서 치즈와 닿으면 녹여주자.
            melt();
            
            // 남은 치즈 칸 개수 갱신 
            if(total != 0) res = total;
        }
        
    }
 
    private static void melt() {
        
        Queue<Point> q = new LinkedList<>();
        boolean[][] visited = new boolean[R][C];
        // (0,0)은 무조건 공기
        q.add(new Point(0, 0));
        visited[0][0] = true;
        
        while(!q.isEmpty()) {
            Point now = q.poll();
            // 4방 탐색
            for (int d = 0; d < 4; d++) {
                int xx = now.x + dx[d];
                int yy = now.y + dy[d];
                // 범위를 벗어나면
                if(xx < 0 || xx >= R || yy <0 || yy >= C) continue;
                // 이미 방문한 좌표
                if(visited[xx][yy]) continue;
                // 치즈가 있을 경우
                if(map[xx][yy] == 1) {
                    // 치즈를 녹여주자
                    map[xx][yy] = 0;
                    visited[xx][yy] = true;
                    total--;
                    continue;
                } else { // 공기일 경우에만 queue에 add
                    visited[xx][yy] = true;
                    q.add(new Point(xx, yy));
                }
            }
        }
        
    }
 
}
 
 

#. Code_v2

이 코드는 O(N^2)에 해결한 방법이다.

정말 배울 점이 많은 코드였다.

1. 0/1 입력 처리

0과 1이 입력일 경우 boolean 배열을 사용하기 위해

 map[i][j] = (st.nextToken().charAt(0) - '0' == 1) 

이렇게 해준 방법은 정말 좋은 방법 같다.

여기서 조건문까지 적용해서 Count까지 해주는 방법..!

if (map[i][j] = (st.nextToken().charAt(0) - '0' == 1)) {

     cheeze++;

}

2. LinkedList 배열

LinkedList<Point>[] q = new LinkedList[2];

q[0] = new LinkedList<>();

q[1] = new LinkedList<>();

LinkedList 배열은 생각도 못 해본건데 정말 유용하게 사용할 수 있을 것 같다.

3. curr, next 교차

int curr = 0, next = 1;

..

curr ^= 1;

next ^= 1;

/*
reference : laeag
*/
 
import java.awt.Point;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class BOJ2636_v2 {
    
    static int R, C, cheeze, time, prevCnt;
    static boolean[][] map;
    static int[] dr = {-1, 0, 1, 0}, dc = {0, -1, 0, 1};
    
    public static void main(String args[]) throws Exception {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
 
        map = new boolean[R][C];
        for (int i = 0; i < R; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < C; j++) {
                // 초기 치즈 칸 count
                if (map[i][j] = (st.nextToken().charAt(0) - '0' == 1)) {
                    cheeze++;
                }
            }
        }
 
        go();
        
        System.out.println(time);
        System.out.println(prevCnt);
    }
 
    private static void go() {
        
        int cnt = 0;
        boolean[][] visited = new boolean[R][C];
        // 공기와 닿은 치즈의 좌표를 저장하는 queue[curr]
        // 공기의 좌표를 저장하는 queue[next]
        LinkedList<Point>[] q = new LinkedList[2];
        q[0] = new LinkedList<>();
        q[1] = new LinkedList<>();
 
        q[0].offer(new Point(0, 0));
        int curr = 0, next = 1;
        while (cheeze > 0) {
            while (!q[curr].isEmpty()) {
                Point now = q[curr].poll();
                // 4방 탐색
                for (int d = 0; d < 4; d++) {
                    int rr = now.x + dr[d];
                    int cc = now.y + dc[d];
                    // 범위를 벗어남
                    if(rr < 0 || rr >= R || cc < 0 || cc >= C) continue;
                    // 이미 방문
                    if(visited[rr][cc]) continue;
                    
                    visited[rr][cc] = true;
                    // 치즈일 경우
                    if(map[rr][cc]) {
                        // 녹여주고
                        map[rr][cc] = false;
                        // 치즈의 테두리를 저장
                        q[next].add(new Point(rr, cc));
                        cheeze--;
                    } else { // 공기일 경우
                        q[curr].add(new Point(rr, cc));
                    }
                }
            }
            curr ^= 1;
            next ^= 1;
            cnt++;
        }
 
        time = cnt;
        prevCnt = q[curr].size();
    }
}