[Gold IV] 치즈 - 2636 (Java)

 

문제 링크

성능 요약

메모리: 18484 KB, 시간: 204 ms

분류

너비 우선 탐색, 그래프 이론, 그래프 탐색, 구현, 시뮬레이션

 

문제 설명

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

이 치즈를 공기 중에 놓으면 녹게 되는데 공기와 접촉된 칸은 한 시간이 지나면 녹아 없어진다. 치즈의 구멍 속에는 공기가 없지만 구멍을 둘러싼 치즈가 녹아서 구멍이 열리면 구멍 속으로 공기가 들어가게 된다. <그림 1>의 경우, 치즈의 구멍을 둘러싼 치즈는 녹지 않고 ‘c’로 표시된 부분만 한 시간 후에 녹아 없어져서 <그림 2>와 같이 된다.

<그림 1> 원래 치즈 모양

다시 한 시간 후에는 <그림 2>에서 ‘c’로 표시된 부분이 녹아 없어져서 <그림 3>과 같이 된다.

<그림 2> 한 시간 후의 치즈 모양

<그림 3> 두 시간 후의 치즈 모양

<그림 3>은 원래 치즈의 두 시간 후 모양을 나타내고 있으며, 남은 조각들은 한 시간이 더 지나면 모두 녹아 없어진다. 그러므로 처음 치즈가 모두 녹아 없어지는 데는 세 시간이 걸린다. <그림 3>과 같이 치즈가 녹는 과정에서 여러 조각으로 나누어 질 수도 있다.

입력으로 사각형 모양의 판의 크기와 한 조각의 치즈가 판 위에 주어졌을 때, 공기 중에서 치즈가 모두 녹아 없어지는 데 걸리는 시간과 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 치즈가 없는 칸은 0, 치즈가 있는 칸은 1로 주어지며 각 숫자 사이에는 빈칸이 하나씩 있다.

 

출력

첫째 줄에는 치즈가 모두 녹아서 없어지는 데 걸리는 시간을 출력하고, 둘째 줄에는 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 출력한다.

 

풀이 (BFS) 

시간 복잡도 O(N*M) 공간 복잡도 O(N*M)

아이디어: 2가지 로직을 사용(1. 내부의 공기(0)와 외부 공기(2)로 구분짓기, 2. 치즈녹이기)

1: 2번 작업을 하기전에 0,0 제일 우측 공간부터 시작하여 BFS를 사용하여 전체 탐색으로 내부 공기와 외부 공기를 구분짓는다.

2: Map[i][j]가 1이라면 BFS를 사용하여 전체 탐색 치즈(1) 주변에 외부 공기(2)가 있다면 해당 위치를 따로 저장하고 이후

탐색이 종료된다면 저장된 공간을 전부 공기(2)로 바꿔준다.   

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

class Pos{
    int c,r;
    Pos(int c,int r){
        this.c=c;
        this.r=r;
    }
}

public class Main {
    public static int sti(StringTokenizer st){
        return Integer.parseInt(st.nextToken());
    }
    public static long stl(StringTokenizer st){
        return Long.parseLong(st.nextToken());
    }
    static int[][] M;
    static boolean[][] visited;
    static boolean[][] isTarget;
    static int[][] ways = {{1,0},{-1,0},{0,1},{0,-1}};
    static ArrayList<Pos> targets;
    static int remain;
    public static boolean isOut(int C,int R){
        return C<0||C>=M.length||R<0||R>=M[0].length;
    }
    public static void judgeAir(int c, int r){
        Deque<Pos> q = new ArrayDeque<>();
        q.add(new Pos(c, r));
        while (!q.isEmpty()) {
            Pos cur = q.poll();
            for (int[] way : ways) {
                int C = way[0] + cur.c;
                int R = way[1] + cur.r;
                if (isOut(C, R) || M[C][R] == 1 || visited[C][R]) continue;
                M[C][R] = 2; // 외부 공기 표시
                q.add(new Pos(C, R));
                visited[C][R] = true;
            }
        }
    }
    public static void bfs(int c,int r){
        Deque<Pos> q = new ArrayDeque<>();
        targets = new ArrayList<>();
        q.add(new Pos(c,r));

        while(!q.isEmpty()){
            Pos cur = q.poll();

            for(int[] way: ways){
                int C = way[0]+cur.c;
                int R = way[1]+cur.r;
                if(isOut(C,R)) continue;

                if(!isOut(C,R)&&!visited[C][R]) {
                    q.add(new Pos(C, R));
                    visited[C][R] = true;
                }
                // 이미 검사하는 칸이 들어가있다면 다음 반복으로
                if(isTarget[cur.c][cur.r]) continue;

                // 현재가 공기이고 이동 하기 전 위치가 치즈인 경우
                if(M[cur.c][cur.r]==1&&M[C][R]==2&&!isTarget[cur.c][cur.r]) {
                   targets.add(new Pos(cur.c,cur.r));
                   isTarget[cur.c][cur.r] = true;
                }

            }
        }

        remain = targets.size();
        // 적용
        for (Pos target : targets) {
             M[target.c][target.r] = 2;
        }

    }
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int C = sti(st), R = sti(st);
        M = new int[C][R];
        isTarget = new boolean[C][R];
        int time = 0;

        for (int i = 0; i < C; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < R; j++) {
                M[i][j] = sti(st);
            }
        }

        for (int i = 0; i < C; i++) {
            for (int j = 0; j < R; j++) {
                if(M[i][j]==1) {
                    visited = new boolean[C][R];
                    judgeAir(0,0);
                    visited = new boolean[C][R];
                    visited[i][j] = true;
                    bfs(i, j);
                    time++;
                }
            }
        }
        System.out.println(time);
        System.out.println(remain);

    }
}

 

개선된 풀이 (BFS) 

차이점: 위에 풀이 방식은 M[][]을 무조건 적으로 전체 탐색하여 녹일 치즈를 따로 배열에 저장하고 탐색이 끝난 후에 반영하는 것을 M[][]에 치즈가 발견된다면 계속 반복하는 방식인 반면

아래의 풀이는 녹여야하는 치즈의 숫자와 위치 정보를 파악하고 해당 부분의 주변만 탐색하여 다음 반복에 처리해야할 치즈의 정보를 저장하고 외부공기로 전환되는 내부공기를 찾아내 처리하는 방식을 반복함으로써 최소한의 탐색을 통해 문제를 처리하고 있다. 

시간 복잡도 O(N*M) 공간 복잡도 O(N*M)

아이디어: 2가지 로직을 사용(1. 내부의 공기(0)와 외부 공기(2)로 구분지으면서 녹일 치즈 정보 저장하기, 2. 치즈 녹이기, 치즈 정보 저장)

1: BFS를 사용하여 전체 탐색으로 내부 공기와 외부 공기를 구분지음과 동시에 공기와 맞닿아 녹여져야하는 치즈를 따로 큐에 저장한다.

2: 녹여야되는 수 만큼의 치즈만큼 반복하여 치즈를 녹임과 동시에 BFS를 사용하여 탐색하여 녹여진 치즈와 맞닿은 내부 공기가 있다면 1번 작업을 통해 외부공기로 바꾸어주고, 다음 반복에 녹일 치즈의 정보를 저장한다.

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

public class Main {
    public static int sti(StringTokenizer st){
        return Integer.parseInt(st.nextToken());
    }
    public static long stl(StringTokenizer st){
        return Long.parseLong(st.nextToken());
    }
    static int[][] map;
    static boolean[][] visited;
    static Queue<int[]> cq = new ArrayDeque<int[]>();
    static int[][] ways = {{1,0},{-1,0},{0,1},{0,-1}};
    public static boolean isOut(int C,int R){
        return C<0||C>=map.length||R<0||R>=map[0].length;
    }
    public static void judgeAir(int c, int r){
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[]{c,r});
        map[c][r] = 2;

        while(!q.isEmpty()){
            int[] cur = q.poll();

            for(int[] way: ways){
                int C = way[0]+cur[0];
                int R = way[1]+cur[1];
                if(isOut(C,R)) continue;

                if(map[C][R]==0){
                    map[C][R]=2;
                    q.add(new int[]{C,R});
                }

                // 외부 공기와 닿은 치즈의 위치 삽입
                if(!visited[C][R]&&map[C][R]==1) {
                    cq.add(new int[]{C,R});
                    visited[C][R] = true;
                }
            }
        }
    }
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int C = sti(st), R = sti(st);
        map = new int[C][R];
        visited = new boolean[C][R];

        for (int i = 0; i < C; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < R; j++) {
                map[i][j] = sti(st);
            }
        }
        int time = 0;
        int rec = 0;
        judgeAir(0,0);

        while(!cq.isEmpty()){
            time++;
            int size = cq.size();
            rec = size;

            // 삽입된 치즈의 수 만큼 반복
            for (;size>0;size--){
                int[] cur = cq.poll();
                // 치즈가 없는 경우는 없으므로 Null 포인트 x 치즈 녹이기
                map[cur[0]][cur[1]] = 2;

                for (int[] way : ways) {
                    int nC = way[0]+cur[0];
                    int nR = way[1]+cur[1];
                    if(isOut(nC,nR)) continue;
                    // 내부 공기가 녹아야 하는 부분과 맞닿아 있다면 외부 공기 처리
                    if(map[nC][nR]==0)
                        judgeAir(nC,nR);
                    // 다음 반복에 사용될 치즈 추가하기
                    else if(!visited[nC][nR]&&map[nC][nR]==1){
                        cq.add(new int[]{nC,nR});
                        visited[nC][nR] = true;
                    }
                }
            }
        }
        System.out.println(time + "\n" + rec);
    }
}