백준 [자바 java] 2573 : 빙산

정말정말정말 오랜만에 알고리즘 문제를 풀었다. 

감이 많이 줄어든 것 같다. 앞으로 좀 가끔이라도 풀어야겠다.

 

문제

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

 

해설

이 문제는 크게 두가지 문제가 있다.

• 1년뒤 빙하의 배열을 만들기
• 빙하의 덩어리 수를 체크하기

빙하 덩어리 확인하기

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

우선 x,y 좌표를 스택에 저장하기 위해서 클래스를 하나 만들었다.

 

    int[] dx = {0,1,0,-1};
    int[] dy = {1,0,-1,0};

또한 dx, dy 테크닉을 사용하기 위해서 위와 같은 배열을 만들었다.

 

Stack<xy> stack = new Stack<>();
int[][] vis = new int[n][m];

int fin = 0;

for(int i = 0;i<n;i++){
  for(int j = 0;j<m;j++){
    if(arr[i][j] !=0 && vis[i][j] == 0){
      if(fin == 1){
        System.out.println(answer);
        System.exit(0);
      }
      stack.push(new xy(i,j));
      while(!stack.isEmpty()){
        //System.out.println(8);
        xy xy = stack.pop();
        if(vis[xy.x][xy.y] == 1) continue;
        vis[xy.x][xy.y] = 1;
        //System.out.println(arr[xy.x][xy.y]);
        for(int k =0;k<4;k++){
          //0 갯수 구하기
          int xx = xy.x + dx[k];
          int yy = xy.y + dy[k];

          if(xx >= 0 && xx <n && yy >= 0 && yy < m){
            if(arr[xx][yy] != 0 && vis[xx][yy] == 0){
              stack.push(new xy(xx,yy));
            }
          }
        }
      }
      fin =1;
    }
  }
}

이 부분이 빙하의 덩어리를 확인하는 부분이다. dfs를 통해서 파악하였다. 여기서는 덩어리의 갯수가 중요한 것이 아니라 덩어리가 두개 이상이냐가 중요하으로, 만약 덩어리 하나를 탐색했는데 또 다른 덩어리가 나오면 바로 끝내기로 했다.

 

오랜만에 하니까 vis 부분을 업데이트 하는 코드의 위치를 헷갈렸었다. 주의해야겠다.

 

빙산 깎기

int[][] arr2 = new int[n][m];

      //빙산 깎아냄
      for(int i = 0;i<n;i++){
        for(int j = 0;j<m;j++){
          int zero = 0;
          if(arr[i][j] == 0) continue;
          for(int k =0;k<4;k++){
            //0 갯수 구하기
            int xx = i + dx[k];
            int yy = j + dy[k];
            if(xx >= 0 && xx <n && yy >= 0 && yy < m){
              if(arr[xx][yy] == 0){
                zero++;
              }
            }
          }
          if(zero != 0){
            if(arr[i][j] - zero <= 0){
              arr2[i][j] = 0;
            }
            else{
              arr2[i][j] = arr[i][j] - zero;
            }
            change++;
          }
          else{
            arr2[i][j] = arr[i][j];
          }
        }
      }

      arr = arr2.clone();


      if(change == 0){
        System.out.println(0);
        System.exit(0);
      }

      answer++;
    }

위 코드에서는 빙하를 깎는다. 0이 아닌 좌표의 상하좌우를 탐색하여, 0인 좌표의 갯수를 구하고 배열을 업데이트 한다.

 

이 때 처음 입력받았던 arr에 바로 업데이트를 하면 오류가 발생한다. 꼭 다른 배열에 업데이트를 먼저 하고 옮겨야한다.