[소프티어] 동계 테스트 시점 예측(JAVA)

문제

https://softeer.ai/practice/6281

---

풀이(25분)

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

public class Main {
    // Queue를 두개 들고 다니자!
    // 한 개는 얼음이 녹을 큐, 한 개는 외부 공기가 유입이 되는 큐
    static int n, m;
    static int[][] ice; // 2는 외부와 맞닿아 있으며 얼음 없음, 1은 얼음 있음, 0는 내부에 갇힘
    static int[] dx = new int[]{0, 0, -1, 1};
    static int[] dy = new int[]{-1, 1, 0, 0};
    static Queue<Point> melting = new LinkedList<>();
    static Queue<Point> icePoint = new LinkedList<>();
    static Queue<Point> external = new LinkedList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());

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


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

        Queue<Point> edges = new LinkedList<>(); // 초기 내부 공간 초기화

        for(int i = 0; i < n; i++){ // 격자 추가
            edges.add(new Point(i, 0));
            edges.add(new Point(i, m-1));
        }

        for(int j = 1; j < m - 1; j++){ // 격자 추가
            edges.add(new Point(0, j));
            edges.add(new Point(n-1, j));
        }

        setInternal(edges); // 내부 공간 초기화

        int time = 0;
        while(!icePoint.isEmpty()){
            time++;
            int icePointSize = icePoint.size();
            for(int i = 0; i < icePointSize; i++){ // 녹을 것들부터 확인
                Point cur = icePoint.poll();
                boolean check = check(cur);
                if(check){
                    melting.add(cur);
                }else{
                    icePoint.add(cur);
                }
            }
            setMelting(); // 확인된 것들 녹임
            setExternal(); // 외부와 닿은 것 있으면 확인
        }
        System.out.println(time);
    }

    static void setExternal(){ // 내부를 외부와 연결
        while(!external.isEmpty()){
            Point cur = external.poll();
            ice[cur.x][cur.y] = 2;
            for(int i = 0; i < 4; i++) {
                int nextX = cur.x + dx[i];
                int nextY = cur.y + dy[i];
                if (nextX >= 0 && nextX < n && nextY >= 0 && nextY < m) {
                    if (ice[nextX][nextY] == 0) {
                        external.add(new Point(nextX, nextY));
                    }
                }
            }
        }
    }

    static void setMelting(){ // 녹이기
        while(!melting.isEmpty()){
            Point cur = melting.poll();
            ice[cur.x][cur.y] = 2;
            for(int i = 0; i < 4; i++) {
                int nextX = cur.x + dx[i];
                int nextY = cur.y + dy[i];
                if (nextX >= 0 && nextX < n && nextY >= 0 && nextY < m) {
                    if (ice[nextX][nextY] == 0) { // 만약 내부와 외부를 연결하고 있었다면
                        external.add(new Point(nextX, nextY)); // 내부 뚫어주기
                    }
                }
            }
        }
    }
    static boolean check(Point cur){ // 녹을 수 있는지 확인
        int count = 0;
        for(int i = 0; i < 4; i++) {
            int nextX = cur.x + dx[i];
            int nextY = cur.y + dy[i];
            if (nextX >= 0 && nextX < n && nextY >= 0 && nextY < m) {
                if (ice[nextX][nextY] == 2) {
                    count++;
                }
            }
        }
        if(count >= 2){
            return true;
        }
        return false;
    }

    static void setInternal(Queue<Point> edges){ // 내부와 외부의 빈 공간 구분
        while(!edges.isEmpty()){
            Point cur = edges.poll();
            if(ice[cur.x][cur.y] == 2){
                continue;
            }
            ice[cur.x][cur.y] = 2;
            for(int i = 0; i < 4; i++){
                int nextX = cur.x + dx[i];
                int nextY = cur.y + dy[i];
                if(nextX >= 0 && nextX < n && nextY >= 0 && nextY < m){
                    if(ice[nextX][nextY] == 0){
                        edges.add(new Point(nextX, nextY));
                    }
                }
            }
        }
    }

    static class Point{ // 좌표 기록 클래스
        int x, y;

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

}

---

문제 풀이 전략

 

세부적인 반복에 집중해도 좋지만, 항상 큰 그림을 보자.

이 문제의 경우 격자는 각 100까지 가능한 꽤 범위가 큰 문제였다.

잘못하면 bfs 등을 사용하더라도 시간초과가 발생할 수 있다.(4방향 탐색을 하는 것이 꽤 큰 연산이다.)

그렇기에 문제를 효율적으로 풀이하기 위해 단계를 구분하고, 그에 따른 메서드를 분리했다.

외부와 내부를 먼저 결정하자.

얼음이 없는 부분이라고 해도 동일한 상태가 아니다.

외부인 것이 있고, 내부에 갇혀있는 부분이 있다. 이것을 구분하기 위해 2와 0이라는 상태를 구분시켰다.

먼저 처음에 입력을 받으면 모두 내부에 있는 것으로 가정한다.

이후 격자 부분에 얼음이 없다는 것을 이용하여, 모든 격자 부분에 대해 bfs를 통해 외부에 있는 얼음이 없는 부분을 모두 체크해 준다.

 

일단 반복이 시작될 때 시간을 1초 더해준다.

녹을 수 있는 얼음을 모두 확인하자.

모든 좌표에 대해 탐색을 하며 녹을 수 있는 얼음을 확인하는 것이 아니라, 초기 입력을 받을 때 모든 얼음의 좌표를 저장한다.

이후 과정은 다음과 같다.

• 모든 얼음에 대해 for문을 통해 검사한다.
  • 최대 반복 크기는 초기 icePointSize와 동일하다.
  • 통과했다면 melting 큐에 넣어준다.
  • 통과하지 못했다면, 다시 icePoint에 넣어준다.
  • 이때 check() 메서드를 통해 외부와 두 번 이상 닿았는지 확인해 준다.

녹일 수 있는 얼음을 녹이자.

setMelting() 메서드를 통해 녹을 수 있다고 확인된 얼음을 녹이자.

여기서 중요한 것은 단순하게 녹이는 것이 아니라 4방향 탐색을 하며, 이 얼음이 녹음으로 인해서 외부와 내부가 연결될 수 있는지 확인해준다.

• 만약 4방향 탐색 중 0인 값(내부를 의미한다)을 찾으면 external 큐에 추가한다.

외부와 내부를 연결하자.

external 큐에 Point가 들어있다면 외부와 내부가 연결되었다는 것이다.

다음 반복을 진행하기 이전에 상태값을 0 → 2로 수정해 주자!

 

코드가 길어지기 때문에 반드시 수도코드 혹은 아이디어를 명확하게 작성해 두고, 중간중간 주석을 통해 꼼꼼하게 진행하자.