빙산(백준_2573)

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

2573번: 빙산

문제설명

제일 처음 2차원 배열에 빙산의 정보가 들어가 있다.

그림 2는 1년후 그림 3은 2년 후의 빙산의 상태이다.

제일 처음 그림 1처럼 2차원 배열에 빙산의 현재 상태를 알려준다. 비어있는 부분은 모두 0이다. 빙산은 1년이 지날 경우 주변에 0의 갯수만큼 줄어든다. 즉 상하좌우에 0의 갯수가 2개라면 그 빙산은 2만큼 크기가 줄어든다.

 

문제에 대한 아이디어

처음에 생각한 방법

• 2차원 배열에서 0인 부분은 넘어간다.
• 0이 아닌부분은 상하좌우에 0의 갯수를 count한 뒤 그만큼 빼준다.(만약 0보다 작으면 0으로 만든다) 
• BFS를 통해 이어진 빙산의 갯수를 count한다.

 

틀린 이유

• 같은 연도에 0이 된 빙하는 0으로 count하면 안된다.
• 모든 부분을 탐색하므로 시간이 오래걸린다.

 

개선한 방법

• check 이차원 배열을 하나 만들어서 이번 년도에 0이 된 빙하는 check를 해준다.
• ArrayList를 하나 만들어서 빙하가 있는 좌표를 저장해 둔 뒤 거기만 탐색한다.

 

구현

• 사용하는 변수 및 자료구조

static class Pair{ // Pair 처리
    int y,x;
    Pair(int y, int x){
        this.y = y;
        this.x = x;
    }
}
static int n = 0;
static int m = 0;
static int dx[] = {1,-1,0,0};
static int dy[] = {0,0,1,-1};
static int arr[][]; // 입력 이차원 배열
static int year = 0; // 정답
static int zero_count = 0; // 주변에 0이 몇개인지 세기
static boolean visited[][]; // 방문했는지 검사
static boolean check[][]; // 방금 녹았는지 검사
static int result=0; // 연결된 빙산의 갯수
static ArrayList<Pair> ar; // 지금 빙산이 있는 좌표 모음

• Main

public static void main(String[] args) throws IOException {
    BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(buf.readLine());
    n = Integer.parseInt(st.nextToken());
    m = Integer.parseInt(st.nextToken());
    ar = new ArrayList<>(); // 빙하의 좌표 저장할 ArrayList
    arr = new int[n][m]; 
   
    for (int i = 0; i < n; i++) {
        st = new StringTokenizer(buf.readLine());
        for (int j = 0; j < m; j++) {
            arr[i][j] = Integer.parseInt(st.nextToken());
            if(arr[i][j] >0) ar.add(new Pair(i,j));
        }
    }
    
    while(true) {
        check = new boolean[n][m];
        visited = new boolean[n][m];
        sol(); // 1년 진행 후
        ++year;
        //1년 진행 후 빙하가 있는 곳이 없으면 year = 0
        if(ar.size() == 0){
            year=0;
            break;
        }
        //빙하가 있는 부분을 기준을 BFS 탐색
        for(Pair pa : ar){
            if(arr[pa.y][pa.x] <= 0 || visited[pa.y][pa.x] == true) continue;
            else {
                BFS(pa.y,pa.x);
                ++result;
            }
        }
        if(result >= 2) break;
        result = 0;
    }
    System.out.println(year);
}

• Sol 메소드(1년 진행하는 함수)

static void sol(){ 
//개발하다가 ArrayList를 쓸 경우 ArrayList에서 요소를 삭제할 때 앞에 요소 부터 삭제하면 에러를 발생시킬 수 있음
    for (int i = ar.size()-1; i >= 0 ; i--) {
        int nowY = ar.get(i).y;
        int nowX = ar.get(i).x;
        if (arr[nowY][nowX] == 0) continue;
        else {
            for (int k = 0; k < 4; k++) {
                int ny = nowY + dy[k];
                int nx = nowX + dx[k];
                if (nx < 0 || nx >= m || ny < 0 || ny >= n) {
                    continue;
                }
                if (arr[ny][nx] == 0 && check[ny][nx] == false) {
                    zero_count++;
                }
            }
            arr[nowY][nowX] -= zero_count;
            ar.remove(ar.get(i));
            if(arr[nowY][nowX] > 0) ar.add(new Pair(nowY, nowX));
            if (arr[nowY][nowX] <= 0) {
                arr[nowY][nowX] = 0;
                check[nowY][nowX] = true;
            }
            zero_count = 0;
        }
    }
}

• BFS

static void BFS(int y, int x){ // 붙어있는 빙산 탐색
    if(visited[y][x] == true) return;
    visited[y][x] = true;
    for (int i = 0; i < 4; i++) {
        int ny = y + dy[i];
        int nx = x + dx[i];
        if(arr[ny][nx] > 0) BFS(ny,nx);
    }
}

 

전체코드

https://github.com/Heron-Woong/CodingTest_Practice/blob/main/%EB%B0%B1%EC%A4%80_2573.java

GitHub - Heron-Woong/CodingTest_Practice