백준 2573 - 빙산

Java

2573 번 - 빙산

문제

접근 방법

빙산을 녹인다음 BFS를 사용하여 빙산의 개수를 구한다.
주의할 점은, 한 칸마다 값을 변경하면 다른 칸에 영향을 받기 때문에 따로 백업 (hasIce)를 두어 혼선을 방지한다.

코드

import java.util.*;
import java.io.*;

public class Main {
	static int n, m, result;
	static int[][] map;
	static boolean[][] hasIce;		// 빙산이 있는지 확인
	static boolean[][] vis;
	static int[] dy = {-1, 1, 0, 0};
	static int[] dx = {0, 0, -1, 1};
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk = new StringTokenizer(br.readLine());
    	n = stoi(stk.nextToken());
    	m = stoi(stk.nextToken());

    	map = new int[n][m];
    	hasIce = new boolean[n][m];

    	for(int i = 0; i < n; i++) {
    		stk = new StringTokenizer(br.readLine());
    		for(int j = 0; j < m; j++) {
    			map[i][j] = stoi(stk.nextToken());
    		}
    	}

    	int iceCnt = 0;
    	int year = 1;
    	int ny,nx, cnt;
    	while(true) {
    		// 빙하의 존재 여부를 확인한다
    		hasIce = new boolean[n][m];
    		for(int y = 1; y < n - 1; y++) {
    			for(int x = 1; x < m - 1; x++) {
    				if(map[y][x] != 0) {
						hasIce[y][x] = true;
					}
    			}
    		}

    		iceCnt = 0;
    		// 빙하를 녹인다.
    		for(int y = 1; y < n - 1; y++) {
    			for(int x = 1; x < m - 1; x++) {
        			if(map[y][x] != 0) {
        				iceCnt++;
        				// 상 하 좌 우에 빙산이 있는지 확인
        				for(int k = 0; k < 4; k++) {
        					ny = y + dy[k];
        					nx = x + dx[k];

        					if(!hasIce[ny][nx]) {
        						map[y][x]--;
        					}

        					if(map[y][x] < 0) {
        						map[y][x] = 0;
        						break;
        					}
        				}
        			}
        		}
    		}

    		// 빙하의 개수를 구한다.
    		cnt = 0;
    		vis = new boolean[n][m];
    		for(int y = 1; y < n - 1; y++) {
    			for(int x = 1; x < m - 1; x++) {
    				if(map[y][x] != 0 && !vis[y][x]) {
    					cnt++;
    					BFS(y,x);
					}
    			}
    		}

    		if(cnt >= 2) {
    			break;
    		}

    		// 모든 빙산이 녹아버릴 시
    		if(iceCnt == 0) {
    			year = 0;
    			break;
    		}

    		year++;
    	}

    	System.out.println(year);
    	br.close();
	}

	private static void BFS(int y, int x) {
		Queue<int[]> queue = new LinkedList<int[]>();
		queue.add(new int[] {y,x});

		int[] q;
		vis[y][x] = true;
		int ny,nx;
		while(!queue.isEmpty()) {
			q = queue.poll();

			y = q[0];
			x = q[1];

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

				if(map[ny][nx] != 0 && !vis[ny][nx]) {
					vis[ny][nx] = true;
					queue.add(new int[] {ny,nx});
				}
			}
		}
	}

	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

개선할 점