[Softeer] 동계 테스트 시점 예측 - Java

https://softeer.ai/practice/info.do?idx=1&eid=411&sw_prbl_sbms_sn=180543 

Softeer

---

1. 문제

NxM 크기의 map이 주어진다.

정사각형의 2개 이상의 변이 외부 공기와 접촉했을 때 녹고, 해당 얼음들은 한 시간 만에 녹는다.

얼음이 모두 녹아 없어지는데 걸리는 정확한 시간을 출력하라.

check point

1. 내부에 있는 공간은 외부 공기와 접촉하지 않는 것으로 가정한다.

2. 맨 가장자리에는 얼음이 놓이지 않는 것으로 가정한다.

 

2. 풀이

bfs문제이다.

백준 치즈처럼 풀려고 하였으나 (외부 공기 bfs, 얼음 bfs, 녹을 얼음 따로 큐에 담고 bfs 끝나면 큐 안에 들은 것들 녹은 걸로 처리)이렇게 하면 시간초과가 나는 것 같다.

다른 사람의 풀이를 보니까 (이중for문+bfs 하나)로 풀었길래 참고해서 풀었다.

 

방법은

1. 외부 공기를 기준으로 하는 것이다. 그래서 bfs의 시작점은 매번 0,0이 된다. (가장자리에는 얼음이 없기 때문)

2. 외부 공기를 따라서 bfs를 진행할 때 map의 값이 1인 지점, 즉 얼음인 지점을 만나게 된다.

이 때 visited를 1 늘려주고 queue에는 넣지 않는다. 반면에 똑같은 외부공기를 만나면 visited에 1증가가 아니라 1을 값으로 넣어주고 queue에 추가해주어 방문 여부를 확인한다.

3. 이렇게 되면 map을 계속해서 탐색하다가 해당 얼음 지점을 다시 만나게 되면 visited가 2로 증가하게 되고, 이것은 외부 공기가 2변 이상 접해있다는 뜻이므로 녹을 대상이 된다.

4. bfs가 끝나면 마지막으로 얼음을 녹여준다. 이중for문으로 map을 돌면서 visited가 2이상인 지점은 외부공기와 2번 이상 닿은 얼음 지점일 것이므로 0으로 갱신해서 녹은 것으로 처리하고 외부공기와 같게 만들어 준다.

5. while문을 돌 때마다 time을 1씩 늘려주어 더 이상 녹을 얼음이 없을 때 빠져나온다.

 

3. 코드

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


public class Main
{
    static int H, W, ans, time;
    static int[][] map, visited;
    static Queue<Pos> queue, melt_queue;
    
    static int[] dy = {-1,1,0,0};
    static int[] dx = {0,0,-1,1};

    public static void main(String args[]) throws Exception
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        H = Integer.parseInt(st.nextToken());
        W = Integer.parseInt(st.nextToken());
        map = new int[H][W];
        
        for (int i=0; i<H; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j=0; j<W; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        } //입력 끝
        
        solution();
        System.out.println(ans);
    }

    static void solution() {
        while (true) {
            int cnt = 0;
            
            visited = new int[H][W];
            for (int i=0; i<H; i++) {
                for (int j = 0; j<W; j++) {
                    if (map[i][j] == 1) {
                        cnt++;
                        bfs();
                    }
                }
            }
            if (cnt == 0) {
                ans = time;
                break;
            }

            for (int i=0; i<H; i++) {
                for (int j=0; j<W; j++) {
                    if (visited[i][j] >= 2) {
                        map[i][j] = 0; //녹음
                    }
                }
            }
            time++;
        }
    }

    static void bfs() {
        queue = new ArrayDeque<> ();
        melt_queue = new ArrayDeque<> ();

        queue.offer(new Pos(0,0));
        visited[0][0] = 1;
        while (!queue.isEmpty()) {
            Pos now = queue.poll();
            for (int d=0; d<4; d++) {
                int ny = now.y+dy[d];
                int nx = now.x+dx[d];
                if (ny<0 || ny>=H || nx<0 || nx>=W) continue;
                //check
                if (map[ny][nx] == 1) {
                    visited[ny][nx]++;
                } else if (map[ny][nx]==0 && visited[ny][nx]==0){
                    visited[ny][nx] = 1;
                    queue.offer(new Pos(ny, nx));
                }
            }
        }
    }

    static class Pos {
        int y, x;
        Pos(int y, int x) {
            this.y = y;
            this.x = x;
        }
    }
}

 

4. 사담

소프티어는 효율을 중요시하는 느낌이다.

매일 알고리즘 푸니까 재밌다. 재밌는 만큼 실력도 빨리 늘기를 바란다..