백준2638: 치즈

풀이1

• DFS를 이용, 치즈가 있는 점을 발견하면 4방면의 칸을 확인, 공기가 있는 칸인 경우 DFS를 통해 치즈 내부 공기인지 아닌지 판별했다.
• 깊은 복사를 이용해서 제거한 치즈가 다음 시행에 영향이 가지 않게 했다.

결과 : 메모리 초과

• 너무 복잡하게 접근한 것 같다. 이미 탐색이 끝난 경우를 기록해서 시간을 단축하고자 했지만, DFS가 빈 칸마다 실행되었기에 실패한 것 같다.

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

public class Problem2638 {
    static int[][] map;
    static int[] xDir = {0,0,1,-1};
    static int[] yDir = {1,-1,0,0};
    static int[][] mapVis;



    //DFS로 map의 마지막 칸에 도달하지 못하면 치즈 안에 갖힌 공간이다
    public static boolean dfs(int[] startNode){


        //복사한 배열에 방문 처리
        mapVis[startNode[1]][startNode[0]] = 1;


        if(startNode[1]==map.length-1 && startNode[0]==map[0].length-1){
            return false;
        }
        for(int i = 0; i < 4; i++){
            int newX = startNode[0] + xDir[i];
            int newY = startNode[1] + yDir[i];

            if(newX>=map[0].length || newX<0 || newY>= map.length || newY<0) continue;
            if(map[newY][newX]==0 && mapVis[newY][newX]==0){
                dfs(new int[]{newX, newY});
            }
        }
        return true;
    }

    //인접한 공기칸의 수를 반환
    public static int adjAir(int[] startNode){
        int answer = 0;


        for(int i = 0; i < 4; i++){
            int newX = startNode[0] + xDir[i];
            int newY = startNode[1] + yDir[i];

            //이미 방문했고 바깥 공기인 경우
            if(map[newY][newX]==2){
                answer++;
            }
            //방문하지 않고, 빈 칸일 경우, 치즈 안 공간이 빈 경우만 answer증가
            else if(map[newY][newX]==0){
                //DFS수행 전 vis배열 초기화
                //map복사
                mapVis = new int[map.length][map[0].length];
                for(int j = 0; j < mapVis.length; j++){
                    System.arraycopy(map[j],0, mapVis[j],0, map[0].length);
                }
                if(dfs(new int[]{newX, newY})){
                    //바깥공기인 경우 "2"로 갱신
                    map[newY][newX] = 2;
                    answer++;
                } else {
                    //치즈 내부 공기일 경우 "3"으로 갱신
                    map[newY][newX] = 3;
                }

            }
        }

        return answer;
    }


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer infoSt = new StringTokenizer(br.readLine(), " ");
        int height = Integer.parseInt(infoSt.nextToken());
        int width = Integer.parseInt(infoSt.nextToken());
        map = new int[height][width];

        for(int h = 0; h < height; h++){
            String wStr = br.readLine();
            StringTokenizer st = new StringTokenizer(wStr, " ");
            for(int w = 0; w < width; w++){
                if(st.nextToken().equals("1")){
                    map[h][w] = 1;
                }
            }
        }

        //DFS방문용처리용 map
        //map복사
        mapVis = new int[map.length][map[0].length];
        for(int i = 0; i < mapVis.length; i++){
            System.arraycopy(map[i],0, mapVis[i],0, map[0].length);
        }


        int days = 0;
        //제거할 칸의 수
        int removeNum = 0;
        while (true){
            removeNum = 0;
            //map복사
            int[][] mapCopy = new int[map.length][map[0].length];
            for(int i = 0; i < mapCopy.length; i++){
                System.arraycopy(map[i],0, mapCopy[i],0, map[0].length);
            }


            //공기에 닿은 칸 제거
            for(int h = 0; h < map.length; h++){
                for(int w = 0; w < map[0].length; w++){
                    if(map[h][w]==1){


                        if(adjAir(new int[]{w, h})>=2){
                            mapCopy[h][w] = 0;
                            removeNum++;
                        }
                    }
                }
            }

            //제거된 칸이 없을 경우
            if(removeNum==0){
                break;
            }

            //map을 갱신된 맵으로 대체
            map = new int[mapCopy.length][mapCopy[0].length];
            for(int i = 0; i < mapCopy.length; i++){
                System.arraycopy(mapCopy[i],0, map[i],0, mapCopy[0].length);
            }
            days++;
        }

        System.out.println(days);


    }
}

풀이 2

• BFS를 이용, 바깥면의 공기를 "2"로 바꾸었고 치즈를 제거했다.
• 내부 공기(0)가 나올 경우 바깥공기인 "2"와 접촉하면 BFS를 시행, 바깥공기로 만들었다.

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

public class Problem2638_2 {
    static int[][] map;
    static int[] xDir = {0,0,1,-1};
    static int[] yDir = {1,-1,0,0};
    static int[][] mapVis;
    static int cheeseNum = 0;

    //바깥 공기 부분을 전부 "2"로 채운다.
    public static void bfs(int[] startNode){
        Queue<int[]> queue = new LinkedList<>();
        //BFS방문용처리용 map
        mapVis = new int[map.length][map[0].length];
        for(int i = 0; i < mapVis.length; i++){
            System.arraycopy(map[i],0, mapVis[i],0, map[0].length);
        }
        queue.add(startNode);
        map[startNode[1]][startNode[0]] = 2;
        mapVis[startNode[1]][startNode[0]] = 1;

        while(!queue.isEmpty()){
            int[] curNode = queue.poll();
            for(int i = 0; i < 4; i++){
                int newX = curNode[0] + xDir[i];
                int newY = curNode[1] + yDir[i];

                if(newX>=map[0].length || newX<0 || newY>= map.length || newY<0) continue;
                if(map[newY][newX]==0 && mapVis[newY][newX]==0){
                    map[newY][newX] = 2;
                    mapVis[newY][newX] = 1;
                    queue.add(new int[]{newX, newY});
                }
            }
        }

    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer infoSt = new StringTokenizer(br.readLine(), " ");
        int height = Integer.parseInt(infoSt.nextToken());
        int width = Integer.parseInt(infoSt.nextToken());
        map = new int[height][width];

        for(int h = 0; h < height; h++){
            String wStr = br.readLine();
            StringTokenizer st = new StringTokenizer(wStr, " ");
            for(int w = 0; w < width; w++){
                if(st.nextToken().equals("1")){
                    map[h][w] = 1;
                    cheeseNum++;
                }
            }
        }

        int days = 0;
        bfs(new int[]{0, 0});
        while (cheeseNum!=0){
            //공기와 인접한 점은 일단"3"으로 만든 뒤, 과정이 끝나면 2로 만든다(전의 결과가 다음 시행에 영향을 주지 않게 한다)
            for(int h = 0; h < height; h++){
                for(int w = 0; w < width; w++){
                    if(map[h][w]==1){
                        int adjNum = 0;
                        for(int i = 0; i < 4; i++) {
                            int newX = w + xDir[i];
                            int newY = h + yDir[i];
                            if(newX>=map[0].length || newX<0 || newY>= map.length || newY<0) continue;

                            if(map[newY][newX]==2){
                                adjNum++;
                            }
                        }

                        if(adjNum>=2){
                            map[h][w] = 3;
                            cheeseNum--;
                        }
                    }
                }
            }
            for(int h = 0; h < height; h++) {
                for (int w = 0; w < width; w++) {
                    if(map[h][w]==3){
                        map[h][w] = 2;
                    }
                }
            }

            //내부 공기가 외부 공기와 닿았을 경우 처리
            for(int h = 0; h < height; h++) {
                for (int w = 0; w < width; w++) {
                    if(map[h][w]==0){
                        for(int i = 0; i < 4; i++) {
                            int newX = w + xDir[i];
                            int newY = h + yDir[i];
                            if (newX >= map[0].length || newX < 0 || newY >= map.length || newY < 0) continue;
                            if(map[newY][newX]==2){
                                bfs(new int[]{w, h});
                            }
                        }

                    }
                }
            }
            days++;

//            System.out.println("--------------------------------");
//            for(int h = 0; h < height; h++) {
//                System.out.println(Arrays.toString(map[h]));
//            }
//            System.out.println(cheeseNum);
//            System.out.println("--------------------------------");
        }
        System.out.println(days);

    }
}