[BOJ 2573] 빙산 - JAVA

골드 4 치곤 쉬웠던 빙산 문제 물론 개인적인 생각입니다...

이 방법은 개인적인 방법이며 최적의 솔루션이 아닐 수 있습니다.

 

우선 문제 먼저 보도록 하겠습니다..!

문제가 길다,,, 그림땜에 길어보이는 것일 수도 있지만..!!!

 

문제설명

1. 일년마다 빙산 주위에 있는 즉, 동서남북에 있는 바다 수만큼 빙산은 줄어든다.(단, 0이하로는 줄지 않는다)

2. 동서남북 방향으로 붙어있는 칸들은 서로 연결된 것으로 하고 연결되어있다면 한 덩어리로 본다.

3. 한 덩어리로 주어진 빙산이 몇 년 후에 2개 이상의 덩어리로 나누어지는지 구하는 문제이다.

 

 

구현방법

이 문제에선 특별히 고민했던 부분은 없습니다...그래서 개인적으로 중요하다고 생각되는 부분을 설명드리겠습다.

(지극히 개인적인 설명) - 저는 BFS를 ㅇㅣ용하여 구현하였습다.

 

1. 바다는 큐에 넣으면 안되고 방문처리를 해선 안됩니다. 단순히 방문 수만 세어야합니다.

2. 빙산이라면 큐에 넣고 방문 수는 세지 않아도 됩니다.

 

더 자세한 설명은 코드 주석을 통해 하도록 하겠습니다.

 

import java.util.*;
import java.io.*;
class Node{
    int x,y;
    Node(int x, int y){
        this.x = x;
        this.y = y;
    }
    int getX() {
        return x;
    }
    int getY() {
        return y;
    }
}
public class Main{
    static int n, m;
    static int[][] graph;
    static boolean[][] visited;
    static int[] dx = {0,0,-1,1};
    static int[] dy = {-1,1,0,0};
    static void bfs(int x, int y) {
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(x, y));
        visited[x][y]=true;
        while(!q.isEmpty()) {
            int k = q.size();
            for(int i=0;i<k;i++) {
                Node node = q.poll();
                x = node.getX();
                y = node.getY();
                int cnt = 0;
                for(int j=0;j<4;j++) {
                    int nx = x+dx[j];
                    int ny = y+dy[j];
                    
                    if(nx>=n||ny>m||nx<0||ny<0)
                        continue;
                    if(visited[nx][ny])
                        continue;
                    if(graph[nx][ny]==0)    //빙산 주위의 바다면의 수를 센다.
                        cnt++;
                    else {
                        visited[nx][ny] = true;    //빙산이라면 큐에 넣는다.
                        q.offer(new Node(nx,ny));
                    }
                }
                /*
                 * 바다면의 수가 빙산 높이 보다 작다면
                 * 빙산의 높이에서 바다면의 수만큼 뺀다
                 */
                if(cnt<graph[x][y])    
                    graph[x][y]-=cnt;
                else
                    graph[x][y] = 0;
            }
        }
    }
      public static void main(String args[]) throws Exception{
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
      StringTokenizer stok = new StringTokenizer(br.readLine());
      
      n = Integer.parseInt(stok.nextToken());
      m = Integer.parseInt(stok.nextToken());
      graph = new int[n][m];
      int cnt = 0;
      for(int i=0;i<n;i++) {
          stok = new StringTokenizer(br.readLine());
          for(int j=0;j<m;j++) {
              graph[i][j] = Integer.parseInt(stok.nextToken());
          }
      }
      
      while(true) {
          visited = new boolean[n][m];    //방문확인 배열
          int island_cnt = 0;    //종료조건
          int zero = 0;    //빙산이 두 개 이상으로 나뉘기전에 모든 빙산이 다 녹는지 확인
          for(int i=0;i<n;i++) {
              for(int j=0;j<m;j++) {
                  if(graph[i][j]!=0&&!visited[i][j]) {
                      bfs(i,j);
                      island_cnt++;
                  }
                  else if(graph[i][j]==0) {
                      zero++;
                      if(zero==n*m)
                          cnt=0;
                  }
              }
          }
          
          if(island_cnt>1||zero==n*m)    //빙산의 개수가 2개이상이거나 모든 빙산이 녹았으면 종료한다.
              break;
          cnt++;
      }
      bw.write(String.valueOf(cnt));
      bw.flush();
   }
}

 

골드 4인데 30분만에 풀게 해줘서 ㄱㅣ분을 좋게 만들어줬던 문제다 ㅎㅎㅎ,,, 내 실력이 늘어서 그랬던거면 더 좋겠다,,,!!!!!