안드 공부를 해볼까?

[Java] 백준 치즈 본문

알고리즘/백준

[Java] 백준 치즈

문바리 2022. 10. 9. 16:21
728x90

1. 문제분석

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

 

2636번: 치즈

아래 <그림 1>과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(<그림 1>에서 네모 칸에 X친 부분)에는 치즈가 놓

www.acmicpc.net

그림이 많아 링크로 올렸다. 외부공기와 접촉하면 치즈가 사라지는 형태다.

필자는 외부공기, 내부공기, 치즈로 나누는거까지 했지만 외부공기를 구하는 식에서 걸렸다.

구글링을 했는데 어짜피 배열의 가장자리는 항상 외부공기이므로 0,0에서 BFS던 DFS던 하면 되는 것 이다.

 

외부공기는 -1, 치즈는 1, 내부공기는 0인 상태로 구분하면 된다.

(0,0)에서 탐색을 시작해 외부공기를 구하고 치즈가 외부공기랑 접하면 0으로 만들면 된다.

여기서 볼점은 DFS를 사용해야하나 BFS를 사용해야하나가 궁금했다.

 

처음은 DFS로 구했다. visited배열을 사용했고 정답도 잘나왔다.

하지만 웬만한 문제는 DFS로 풀린다는 것을 듣고 BFS로도 해봤다. BFS 역시 잘나온다.

여기서 핵심은 DFS는 깊이 탐색, BFS는 넓이 탐색인 것이다. 우리는 깊게 들어가는 것이 아닌 주위에 있는 것을 찾는 것이니 BFS를 사용했다.

첫번째가 DFS고 두번재가 BFS다. 메모리나 시간면에서는 DFS가 빠른 것 같다.

 

정리해보면 외부공기를 구하고 외부공기와 접촉한 치즈는 0으로 변환, 다시 외부공기 구하기가 된다.

2. 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.security.cert.PolicyNode;
import java.util.*;


class Point {
    int x, y;

    Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

public class Main {

    static int[][] arr;
    static int width, height;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static boolean[][] visited;
    static ArrayList<Point> cheeseList = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        height = Integer.parseInt(st.nextToken());
        width = Integer.parseInt(st.nextToken());
        arr = new int[height][width];

        for (int i = 0; i < height; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < width; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int time = 0;
        ArrayList<Integer> meltCheeseList = new ArrayList<>();

        do {
            cheeseList.clear();
            visited = new boolean[height][width];
            searchExternalAirByBFS();
            for (int i = 1; i < height - 1; i++) {
                for (int j = 1; j < width - 1; j++) {
                    if (arr[i][j] == 1 && isMelt(j, i)){
                        arr[i][j] = 0;
                        cheeseList.add(new Point(j,i));
                    }
                }
            }
            //녹인 치즈 개수 구하기
            meltCheeseList.add(cheeseList.size());
            time++;
        } while (cheeseList.size() != 0);

        System.out.println(time - 1);
        System.out.println(meltCheeseList.get(time-2));
    }

    static boolean isMelt(int x, int y) {
        //외부 공기와 접촉된 상태인가?
        for (int i = 0; i < 4; i++) {
            int mx = x + dx[i];
            int my = y + dy[i];

            if (arr[my][mx] == -1) return true;
        }
        return false;
    }

    static void searchExternalAirByBFS(){
        visited[0][0] = true;
        Queue<Point>queue = new LinkedList<>();
        queue.add(new Point(0,0));

        while (!queue.isEmpty()){
            Point p = queue.poll();
            for(int i = 0; i<4; i++){
                int mx = p.x + dx[i];
                int my =p.y + dy[i];

                if(mx < 0 || my < 0 || mx >= width || my >= height) continue;
                if(arr[my][mx] == 1 || visited[my][mx]) continue;
                visited[my][mx] = true;
                arr[my][mx] = -1;
                queue.add(new Point(mx,my));
            }
        }
    }
    static void searchExternalAir(int x, int y) {
        //외부 공기를 dfs로 찾아볼까?
        visited[y][x] = true;
        arr[y][x] = -1;

        for (int i = 0; i < 4; i++) {
            int mx = x + dx[i];
            int my = y + dy[i];

            if (mx < 0 || my < 0 || mx >= width || my >= height) continue;
            if (arr[my][mx] == 1 || visited[my][mx]) continue;
            searchExternalAir(mx, my);
        }
    }
}

외부공기를 구하는 방법을 BFS, DFS 2가지 다 구현했다.

0,0 에서 시작해서 외부공기를 구하고 다 했으면 녹을 치즈인지 구하는 것이다.

녹는 치즈개수는 list에 담았고 출력은 다 녹는 시간, 다 녹기전 치즈를 출력했다.

3. 마무리

이전에는 못풀었던 문제였다. 외부공기를 어떻게 나눌까 고민했는데 이걸 DFS로 풀면 된다는 생각이 딱 들었다.

하지만 시작점이 애매해서 뭐부터 할지 몰라 구글링을 했다. 생각해보니 가장자리는 항상 외부공기인 상태였다.

 

반응형

'알고리즘 > 백준' 카테고리의 다른 글

[Java] 백준 보물섬  (0) 2022.10.10
[Java] 백준 빙산  (0) 2022.10.09
[Java] 백준 치킨 배달  (0) 2022.08.28
[Java] 백준 연구소  (0) 2022.08.27
[Java] 백준 퇴사  (0) 2022.08.27
Comments