백준 2573번. 빙산 (Java)

문제 링크 : https://www.acmicpc.net/problem/2573

빙산 덩어리가 몇년 째에 두 덩어리 이상이 되는 지 계산하는 문제입니다.

<접근>

먼저 빙산이 몇 덩어리 인지는 DFS 로 계산을 하였습니다.

메인 코드에서 DFS 에 들어가는 횟수가 곧 빙산의 갯수입니다.

만약 모든 빙산이 상, 하, 좌, 우로 연결되어 있다면 메인에서 DFS 한번 들어가는 것만으로 모든 빙산을 돌고 나올겁니다.

두번째로 melt 배열을 만들어 녹는 빙산의 높이를 저장하였습니다.

높이는 DFS 를 한번 돌때마다 해당 좌표의 상, 하, 좌, 우를 확인하여 0 인 값이 있으면 melt++ 를 하였습니다.

그리고 빙산의 갯수를 세어 0 개면 0 출력하고 빙산의 갯수가 2개 이상이면 년수를 출력했습니다.

만약 빙산이 아직 한 덩어리라면 높이를 빼주는 melting 함수를 만들었습니다.

2중 for문을 돌면서 빙산의 원래 높이인 map 배열에서 녹은 높이인 melt 배열을 빼줍니다.

그리고 빼준 값이 음수라면 0으로 바꿔줍니다.

이 함수에서 다음 빙산의 갯수를 체크하기 위해 visited 배열과 melt 배열을 초기화해주었습니다.

	import java.util.*;
	import java.io.*;
	// https://www.acmicpc.net/problem/2573
	class Main {
	static int r;
	static int c;
	static int[][] map;
	static int[][] visited;
	static int[][] melt;
	static int[] dx = {1, -1, 0, 0};
	static int[] dy = {0, 0, 1, -1};
	public static void main(String[] args) throws Exception {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st = new StringTokenizer(br.readLine());
	r = Integer.parseInt(st.nextToken());
	c = Integer.parseInt(st.nextToken());
	map = new int[r][c];
	visited = new int[r][c];
	melt = new int[r][c];
	for(int i=0; i<r; i++) {
	st = new StringTokenizer(br.readLine());
	for(int j=0; j<c; j++) {
	map[i][j] = Integer.parseInt(st.nextToken());
	}
	}
	solution();
	}
	static void solution() {
	int year = 0;
	while(true) {
	// dfs 로 빙산 덩어리 세기
	int count = 0;
	for(int i=0; i<r; i++) {
	for(int j=0; j<c; j++) {
	if(visited[i][j] == 0 && map[i][j] != 0) {
	dfs(i, j);
	count++;
	}
	}
	}
	if(count == 0) {
	System.out.println(0);
	break;
	} else if(count >= 2) {
	System.out.println(year);
	break;
	}
	melting();
	year++;
	}
	}
	static void dfs(int x, int y) {
	visited[x][y] = 1;
	for(int i=0; i<4; i++) {
	int nx = x + dx[i];
	int ny = y + dy[i];
	if(0 <= nx && nx < r && 0 <= ny && ny < c) {
	// 1년 후에 녹는 빙산의 양 구하기
	if(map[nx][ny] == 0)
	melt[x][y]++;
	// dfs 재귀
	if(visited[nx][ny] == 0 && map[nx][ny] != 0)
	dfs(nx, ny);
	}
	}
	}
	static void melting() {
	/**
	* 1. 빙산 녹이기
	* 2. 만약 녹인 높이가 음수가 되면 0으로 바꿔주기
	* 3. visited 초기화
	* 4. melt 초기화
	*/
	for(int i=0; i<r; i++) {
	for(int j=0; j<c; j++) {
	map[i][j] -= melt[i][j];
	if(map[i][j] < 0)
	map[i][j] = 0;
	visited[i][j] = 0;
	melt[i][j] = 0;
	}
	}
	}
	}

view raw BOJ2573.java hosted with ❤ by GitHub