[Java] 백준 2573번 : 빙산

1. 문제

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

2573번: 빙산

 

 

2. 풀이 과정

1. 4방향 탐색하면서 빙산이면 dfs탐색하고, 빙산이 아니면 cnt+1을 한다.

2. 한 번 dfs탐색이 끝났는데, 또 dfs탐색할 곳이 남았다면 분리되었다는 것으로 판단하고 종료한다.

3. dfs 탐색이 끝나고 2중 for문으로 전체를 돌면서 주변 0의 개수만큼 숫자를 빼준다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int N, M, map[][], zero[][];
    static int dx[] ={-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
    static boolean visited[][];

    public static void dfs(int x, int y){
        int cnt = 0;
        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx<0 || nx>=N || ny<0 || ny>=M || visited[nx][ny]){continue;}
            if(map[nx][ny]>0){
                visited[nx][ny] = true;
                dfs(nx, ny);
            }
            else{
                cnt++;
            }
        }
        zero[x][y] = cnt;
    }

    public static void go(){
        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                map[i][j] -= zero[i][j];
            }
        }
    }

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][M];

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

        int year = 0;
        outloop : while(true){
            zero = new int[N][M];
            visited = new boolean[N][M];
            int dfsCnt = 0;
            for(int i=0; i<N; i++){
                for(int j=0; j<M; j++){
                    if(map[i][j]<=0 || visited[i][j]){continue;}
                    if(dfsCnt>0){break outloop;}
                    dfsCnt++;
                    visited[i][j] = true;
                    dfs(i, j);
                }
            }
            if(dfsCnt==0){
                year = 0;
                break;
            }
            go();
            year++;
        }
        System.out.println(year);
    }
}

 

결과

풀이시간 30분 + 코드 분석 및 개선 30분