68 삐약 : 백준 2573| 빙산 [바킹독 문제 풀이|BFS|JAVA]

https://www.acmicpc.net/problem/2573

 

package BKD_0x9_BFS;

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

public class BOJ_2573 {
    static int[][] glacier;
    static int[][] visited;

    static int N;
    static int M;
    static int[] dx = {1,-1,0,0};
    static int[] dy = {0,0,1,-1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        glacier = new int[N][M];

        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<M;j++){
                glacier[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int time =0;

        while(true){
            int area =0; // 분리된 빙하 지역 개수
            visited = new int[N][M];

            for(int i=0;i<N;i++){
                for(int j=0; j<M;j++){
                    if(glacier[i][j]>0 && visited[i][j]==0){
                        bfs(i,j);
                        area++;
                    }
                }
            }
            if(area >=2){
                System.out.println(time);
                break;
            }
            if(area==0){
                System.out.println(0);
                break;
            }
            melted();
            time ++;

        }
    }
    // visited 배열을 만드는 이유

    // visited 배열이 없다면,
    // 만약 1 2 가 있는 상태에서 1이 먼저 녹아서 0이 될 경우
    // 2는 녹아서 없어진 1 자리도 0이라고 판단하여
    // 필요 이상으로 더 많은 값을 녹이게 되어 버림.
    static void melted(){
        Queue<Pair> q = new LinkedList<>();
        int[][] map = new int[N][M];

        for(int i=0;i<N;i++){
            for(int j=0; j<M; j++){
                if(glacier[i][j]>0){
                    q.offer(new Pair(i,j));
                    map[i][j]=1;
                }
            }
        }

        while(!q.isEmpty()){
            Pair p = q.poll();
            int count =0;

            for(int k=0;k<4;k++){
                int nx = p.x+dx[k];
                int ny = p.y+dy[k];

                if(glacier[nx][ny]==0 && map[nx][ny]==0) count++;
            }
            glacier[p.x][p.y] = Math.max(0,glacier[p.x][p.y]-count);
        }
    }
    static void bfs(int x, int y){
        Queue<Pair> q = new LinkedList<>();
        visited[x][y]=1;
        q.offer(new Pair(x,y));


        while(!q.isEmpty()){
            Pair p = q.poll();
            for(int i=0;i<4;i++){
                int nx = p.x + dx[i];
                int ny = p.y + dy[i];

                if(nx>=0 && ny>=0 && nx<N && ny<M && visited[nx][ny]==0 && glacier[nx][ny]>0){
                    visited[nx][ny]=1;
                    q.offer(new Pair(nx,ny));
                }
            }
        }
    }

    static class Pair{
        int x;
        int y;

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

 

 

기본적으로 제공되는 간단한 bfs문제인 줄알고 호기롭게 풀었다가 본인의 알고리즘적 생각이 상당히 짧음을 깨달을 수 있는 문제였다 

힝구리핑퐁구리

 

 

문제에서도 확인 할 수 있듯이, 녹은 빙하의 높이를 측정하기 위해서 맞닿아 있는 해수면의 개수를 파악한 뒤 그 개수만큼 높이를 낮추어야 한다.

 

static void melted(){
        for(int i=0;i<N;i++){
            for(int j=0; j<M; j++){
                if(glacier[i][j]>0){
                        int count =0;
                        for(int k=0;k<4;k++){
                            int nx = i+dx[k];
                            int ny = j+dy[k];

                            if(glacier[nx][ny]==0) count++;
                        }
                        glacier[i][j] = Math.max(0,glacier[i][j]-count);
                }
            }
        }

    }

 

그래서 아무 생각 없이 빙하가 녹은 높이를 측정하는 방식을 이렇게 구현하였다.

{이렇게}

1. 상, 하, 좌, 우 좌표에 존재하는 해수면의 개수를 구한다.

2. 해당 개수만큼 빙하의 높이에서 감한 뒤 값을 저장한다.

 

 

이러한 코드로 진행했을 때 가장 큰 문제점은

인접해 있는 빙하가 먼저 녹음으로써 0으로 표기되는 상황이 존재할 경우

그 다음 빙하는 인접해있던 빙하를 이미 녹은 해수면으로 인지하여 더 많은 값을 녹이게 된다. 

 

이러한 이유로 melted 메소드 안에 map이라는 배열을 선언하여 동시에 녹는 빙하인지 파악할 수 있도록 하였다.

static void melted(){
        Queue<Pair> q = new LinkedList<>();
        int[][] map = new int[N][M];

        for(int i=0;i<N;i++){
            for(int j=0; j<M; j++){
                if(glacier[i][j]>0){
                    q.offer(new Pair(i,j));
                    map[i][j]=1;
                }
            }
        }

        while(!q.isEmpty()){
            Pair p = q.poll();
            int count =0;

            for(int k=0;k<4;k++){
                int nx = p.x+dx[k];
                int ny = p.y+dy[k];

                if(glacier[nx][ny]==0 && map[nx][ny]==0) count++;
            }
            glacier[p.x][p.y] = Math.max(0,glacier[p.x][p.y]-count);
        }
    }

 

1. 해수면 위에 떠있는 빙하의 좌표를 큐에 저장한 후, map에 방문 여부를 표기한다.

2. 빙하를 녹이는 행위를 진행할 때 map의 값의 여부를 판독하여 불필요한 빙하의 녹음을 방지한다.