치즈(2636)

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

감도 안왔다... 여기까지가 한계인건가....

그래도 구글링해서 풀어보다보니까 그—-래도 감은 온다 내일 시험이니까 일단은 흐름파악했다는걸로 만족하자

import java.util.*;
import java.io.*;
public class Main{
    static int n, m;
    static int[][] arr;
    static boolean[][] visited;
    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, 1, 0, -1};
    static int time = 0;
    static int result = 0;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        arr = new int[n][m];

        for(int i=0; i<n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<m; j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
                if(arr[i][j] == 1)
                    result++;
            }
        }

        while(true){
            visited = new boolean[n][m];
            outair(0, 0);

            for(int i=0; i<n; i++){
                for(int j=0; j<m; j++){
                    if(arr[i][j] == 1 && isEdge(i, j)){
                        dfs(i, j);
                    }
                }
            }

            change();

            changeAir();
            time++;

            int tmp = countCheese();
            if(tmp!=0){
                result = countCheese();
            }else
                break;
        }
        System.out.println(time);
        System.out.println(result);
        //외부공기는 외부공기로 체크를 해둬야함
        //가장자리 치즈를 확인
    }

    //외부공기를 2로 체크
    public static void outair(int x, int y){
        visited[x][y] = true;
        arr[x][y] = 2;

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

            if(nx<0 || ny<0 || nx>=n || ny>=m)
                continue;
            if(arr[nx][ny]==0 && !visited[nx][ny])
                outair(nx, ny);
        }
    }

    public static void dfs(int x, int y){
        visited[x][y] = true;
        arr[x][y] = -2;

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

            if(nx<0 || ny<0 || nx>=n || ny>=m)
                continue;
            if(arr[nx][ny]==1 && !visited[nx][ny] && isEdge(nx, ny)){
                dfs(nx, ny);
            }
        }
    }

    public static boolean isEdge(int x, int y){
        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(arr[nx][ny] == 2)
                return true;
        }
        return false;
    }

    public static void change(){
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(arr[i][j] == -2)
                    arr[i][j] = 2;
            }
        }
    }

    public static void changeAir(){
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(arr[i][j] == 2)
                    arr[i][j] = 0;
            }
        }
    }

    public static int countCheese(){
        int cnt=0;
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(arr[i][j]==1)
                    cnt++;
            }
        }
        return cnt;
    }
}

BFS버전으로 풀어보기!

import java.io.*;
import java.util.*;

class Main {
    static int n, m;
    static int[][] arr;
    static boolean[][] visited;
    static int cheeseCnt;
    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {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());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        arr = new int[n][m];

        for(int i=0; i<n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<m; j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
                if(arr[i][j] == 1)
                    cheeseCnt++;
            }
        }

        int cnt = 0;
        int time = 0;
        while(cheeseCnt !=0){
            cnt = cheeseCnt;
            time++;
            visited = new boolean[n][m];
            outAir();
        }

        System.out.println(time);
        System.out.println(cnt);
    }

    public static void outAir(){
        visited[0][0] = true;
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{0, 0});
        while(!q.isEmpty()){
            int[] xy = q.poll();
            for(int i=0; i<4; i++){
                int nx = xy[0] + dx[i];
                int ny = xy[1] + dy[i];
                if(nx<0 || ny<0 || nx>=n || ny>=m || visited[nx][ny])
                    continue;
                visited[nx][ny] = true;
                if(arr[nx][ny] == 0){
                    q.add(new int[]{nx, ny});
                }else{
                    cheeseCnt--;
                    arr[nx][ny] = 0;
                }
            }
        }
    }

    public static boolean isEdge(int x, int y){
        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(arr[nx][ny] == 2 )
                return false;
        }
        return true;
    }

    public static int countCheese(){
        int cnt = 0;
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(arr[i][j] == 1)
                    cnt++;
            }
        }
        return cnt;
    }
}