[백준] 2638번 치즈

2638번: 치즈

• 두 변이 공기와 접촉 → 즉, 하나의 칸에서 는 총 네 가지 방향으로 갈 수 있다고 생각 할 수 있는데 ( 문제 조건 상, 가장 자리에는 치즈가 놓이지 않는다!!!! ), 이 중 세 칸이 치즈와 접촉해 있지 않으면 → 녹는다.
  • 단, 이 때, 이런경우가 있다는 : 치즈가 있지 않은 칸인데, 치즈 내부에 있는 공간인 경우.
• 구해야하는 것 : 치즈가 [ 모두 녹아 없어지는데 걸리는 정확한 시간 ]

그리고 문제에 두 개의 예시가 있는데 두번째 예시는 다음과 같다.. 입력으로 안 주어졌길래

8 9
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 1 1 0
0 1 0 1 1 1 0 1 0
0 1 0 0 1 0 0 1 0
0 1 0 1 1 1 0 1 0
0 1 1 0 0 0 1 1 0
0 0 0 0 0 0 0 0 0
//3

풀이 생각

(1:30......... 가장 큰 문제점은...... dfs를 잘못 구현했다는 것이다. next colun, next row를 구할 때는, current r + (r방향이동) , current c+(c방향 이동) 이거여야 하는데 또, next c= nextc + (c방향 이동) 이러고 있었다 )

visit처리가 중요하다.
먼저 외부 비어있는공간들을 모두 탐색해둔다. visit처리를 해 두는 이유는, 치즈내부의 0인공간과의 비교를 위해서다

• (1)주어진 board를 복사해 둔다.
  • visit을 초기화한다.
• (2)먼저 치즈 내부 공간을 찾아서 → copy에서 해당 공간을 "비어있지 않은 공간으로 처리" 해야 한다.
  • 즉, 치즈가 있는 공간으로 처리하자.
  • 이를 위해, 가장자리에서 시작하여 dfs,bfs를 한다. 그러면 이 때 만나는 0인 칸은, 치즈 내부에 있는 칸이 아니기 때문.
  • 가장자리에서 시작하는 dfs,bfs를 한 후에도 0이있는지 확인 → 이 것은, 치즈 내부공간에 해당된다 —> 비어있지 않은 공간으로 처리한다 (copy상에서)ㅡ이를 하는이유는 1인칸중에 인접한 1인칸이 2개 이하인곳을 녹게 할 거라서, 내부에 있는 0인곳은 인접한 1로 여겨야한다. 하지만 이 처리를 copy에서 하는이유는, 후에 내부공간이 즉 치즈내부의 0인곳이 치즈가 녹음으로서 외부공간과 합쳐질 수 있기 때문에. 원본에서는 여전히 0을 유지하고, 치즈가 녹음에 따라 1이었던곳이 0이 됨에 따라, 외부가 된 내부공간도 외부공간으로 탐색된다
• (3)그 후, copy에서 모든 칸을 순회하며, 인접한 네 방향 중, 적어도 세 방향에, 치즈가 있는지 확인한다.
  • 녹아 없어지는 것을 → 원본에 처리한다.
  • 한 시간을 추가한다.
• (1)을 반복한다.

현재풀이는 효율이 매우 안좋다

제출한 사람중 내가 젤 시간 많이 걸리는듯

• 그럴 수 밖에 없는 구현이다. 매번 visit을 초기화하니, 매 번 dfs도 (0,0) 부터 다시하고, 재 방문 하는곳이 기하급수적으로 늘어난다.

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

public class Main {
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static StringTokenizer st;
    public static int n,m;
    public static int time=0;
    public static int[][] board;
    public static int[][] copy;
    public static boolean[][] visit;
    public static int[][] dirs = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
    public static void setting() throws IOException{
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        board = new int[n][m];
        copy = new int[n][m];
        visit = new boolean[n][m];
        for(int r=0;r<n;r++){
            st = new StringTokenizer(br.readLine());
            for(int c=0;c<m;c++){
                board[r][c]=Integer.parseInt(st.nextToken());
            }
        }
    }

    public static void solve(){
        // 먼저 전체 탐색 한 번 -> 치즈가 없으면 0이니까
        if(!nocheese()){
            time=0;
            return;
        }
        int r=0,c=0,cnt=0,dir=0,nr=0,nc=0;
        while(true){

            // copy board into copy array && initiate visit array
            for(int cr=0;cr<n;cr++){
                Arrays.fill(visit[cr],false);
                for(int cc=0;cc<m;cc++)
                    copy[cr][cc]=board[cr][cc];
            }
            // 가장자리에서부터 탐색 : (0,0)에서 시작하면 됨.
            dfs(0,0);

            // 전체를 탐색한다. -> 치즈 내부 비어있는 공간은 1로 만든다
            for(r=0;r<n;r++){
                for(c=0;c<m;c++) {
                    // 방문한 곳은 pass
                    if (visit[r][c]) continue;
                    // 0 인 공간 있나?
                    if (copy[r][c] == 1) continue;
                    copy[r][c] = 1;
                    visit[r][c]=true;
                }
            }

            // 전체를 탐색한다.
            for(r=0;r<n;r++){
                for(c=0;c<m;c++){
                    if(visit[r][c])continue;
                    cnt=0;
                    // 1인 곳만을 visit하지 않게 되었음 -> 4방향을 확인
                    for(dir=0;dir<dirs.length;dir++){
                        nr = r+dirs[dir][0];
                        nc = c+dirs[dir][1];
                        if(copy[nr][nc]==1)cnt++;
                    }
                    if(cnt<=2)board[r][c]=0; //녹아보림 ..
                }
            }

            time++;
            // 치즈 있을까?
            if(!nocheese())break;

        }
    }
    public static boolean nocheese(){
        for(int r=0;r<n;r++){
            for(int c=0;c<m;c++){
                if(board[r][c]==1)return true;
            }
        }
        return false;
    }
    // dfs
    public static void dfs(int sr,int sc){
        visit[sr][sc]=true;
        int nr=sr,nc=sc;
        for(int dir=0;dir<dirs.length;dir++){
            nr = sr+dirs[dir][0];
            nc = sc+dirs[dir][1];
            if(nr<0||nc<0||nr>=n||nc>=m)continue;
            if(visit[nr][nc] ||copy[nr][nc]==1)continue;
            dfs(nr,nc);
        }
    }

    public static void main(String[] args)throws IOException {
        setting();
        solve();
        System.out.println(time);
    }
}

재방문을 줄인 코드

• visit 초기화는 맨 처음 딱 한 번만 한다. 그리고, 이 외부부분에 대한 dfs도 맨 처음에 딱 한 번만 한다.
• 그럼 녹을 때, 내부 공간도 외부공간으로 변하는 건 어떻게 처리하냐?-> 녹을 때 마다, 녹은 곳 부터 dfs를 한다.
  dfs는, 외부공간을 탐색하여, visit처리 시켜주는 역할을 한다.
  visit처리가 중요하다

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

public class Main {
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static StringTokenizer st;
    public static int n,m;
    public static int time=0;
    public static int[][] board;
    public static int[][] copy;
    public static boolean[][] visit;
    public static int[][] dirs = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
    public static void setting() throws IOException{
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        board = new int[n][m];
        copy = new int[n][m];
        visit = new boolean[n][m];
        for(int r=0;r<n;r++){
            st = new StringTokenizer(br.readLine());
            for(int c=0;c<m;c++){
                board[r][c]=Integer.parseInt(st.nextToken());
            }
        }
    }
    public static void solve(){
        // 먼저 전체 탐색 한 번 -> 치즈가 없으면 0이니까
        if(!nocheese()){
            time=0;
            return;
        }
        int r=0,c=0,cnt=0,dir=0,nr=0,nc=0;
        // 가장자리에서부터 탐색 : (0,0)에서 시작하면 됨.
        dfs(0,0);
        // while문을 반복하며 가장자리의 것들이 녹아내린다
        while(true){
            // copy board into copy array && initiate visit array
            for(int cr=0;cr<n;cr++){
                for(int cc=0;cc<m;cc++)
                    copy[cr][cc]=board[cr][cc];
            }
            // 전체를 탐색한다. -> 치즈 내부 비어있는 공간은 1로 만든다
            for(r=0;r<n;r++){
                for(c=0;c<m;c++) {
                    // 방문한 곳은 pass
                    if (visit[r][c]) continue;
                    // 0 인 공간 있나?
                    if (copy[r][c] == 1) continue;
                    copy[r][c] = 1;
                }
            }
            // 전체를 탐색한다.
            for(r=0;r<n;r++){
                for(c=0;c<m;c++){
                    if(visit[r][c])continue;
                    cnt=0;
                    // 1인 곳만을 visit하지 않게 되었음 -> 4방향을 확인
                    for(dir=0;dir<dirs.length;dir++){
                        nr = r+dirs[dir][0];
                        nc = c+dirs[dir][1];
                        if(copy[nr][nc]==1)cnt++;
                    }
                    if(cnt<=2){
                        board[r][c]=0; //녹아보림 ..
                        dfs(r,c); // 녹음으로서 내부공간이 노출 --> 여기서부터 dfs를 해주도록
                    }

                }
            }
            time++;
            // 치즈 있을까? -> 더 없으면 break;
            if(!nocheese())break;
        }
    }
    public static boolean nocheese(){
        for(int r=0;r<n;r++){
            for(int c=0;c<m;c++){
                if(board[r][c]==1)return true;
            }
        }
        return false;
    }
    // dfs
    public static void dfs(int sr,int sc){
        visit[sr][sc]=true;
        int nr=sr,nc=sc;
        for(int dir=0;dir<dirs.length;dir++){
            nr = sr+dirs[dir][0];
            nc = sc+dirs[dir][1];
            if(nr<0||nc<0||nr>=n||nc>=m)continue;
            if(visit[nr][nc] ||board[nr][nc]==1)continue;
            dfs(nr,nc);
        }
    }

    public static void main(String[] args)throws IOException {
        setting();
        solve();
        System.out.println(time);
    }
}

대충 효율이 이렇게 변했다