[백준 온라인 저지(BOJ)] 2573번 빙산 자바 풀이 (bfs 문제)

백준 온라인 저지 2573번 빙산 문제 자바 풀이 입니다.

이는 bfs를 이용하는 문제입니다.

문제 링크는 아래에 있습니다!!

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

 

이 문제는 골드4로 랭크된 문제에요. 하지만 bfs의 개념만 알고 구현할 줄 안다면 그리 어렵지 않습니다.

저는 bfs를 stack을 이용하여 구현하였습니다.

이와 비슷한 문제로 보물섬 문제가 있는데요 백준 2589번도 같이 풀어 보시면 좋을 것 같아요

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

 

문제정리

1. 빙산은 양의 정수, 그 외 바다는 0이다.

2. 빙산에 붙어있는 0의 개수만큼 빙산의 높이가 감소된다. ( 단 빙산의 높이는 0보다 더 줄어들지는 않는다.)

3. 그러다가 빙산이 덩어리로 떨어질 때 두 덩어리로 분리되는 최초의 시간을 구한다.

* 만약 빙산이 다 녹아 없어질때까지 두 덩어리로 분리되지 않는다면 0을 출력한다.

 

문제풀이

1. bfs로 0이 아닌 수를 찾아서 상하좌우를 탐색하여 인접한 0의 개수에 따라 높이 값을 바꿔줍니다.

    * 이때 그때 그때 값을 갱신해주게 되면 녹아서 0으로 된것을 원래 바다로 인식해서 높이가 연쇄적으로

높이가 더 낮아지기 때문에 모든 값을 한 번에 바꿔준다. 저는 리스트에 넣어 놓고 탐색을 마친 후 한 번에 값을 update해주었습니다.

2. 영역의 수는 dfs로 찾으러 들어가는 수로 check한다.

3. 다 녹아서 영역이 0이 된다면 0을 출력하고 끝낸다. 영역이 2가 되는 경우도 출력하고 끝난다.

 

bfs로 탐색하는 부분은 0이 아닌 수들을 계속 따라가면서 그 주변에 붙어있는 0의 개수를 따져 주면 된다.

그러면 간단하게 풀 수 있습니다.

 

백준 2573번 빙산 자바 코드

	import java.io.BufferedReader;
	import java.io.BufferedWriter;
	import java.io.IOException;
	import java.io.InputStreamReader;
	import java.io.OutputStreamWriter;
	import java.util.ArrayList;
	import java.util.Stack;
	class Node{
	int a;
	int b;
	int seaNum;
	Node(int a, int b){
	this.a = a;
	this.b = b;
	this.seaNum = 0;
	}
	Node(int a, int b, int seaNum){
	this.a = a;
	this.b = b;
	this.seaNum = seaNum;
	}
	}
	class Main{
	static int height, width;
	static int[][] map;
	static boolean[][] visited;
	public static void main(String args[]) throws IOException{
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	String[] temp = br.readLine().split(" ");
	height = Integer.parseInt(temp[0]);
	width = Integer.parseInt(temp[1]);
	map = new int[height][width];
	for(int i=0; i<height; i++) {
	String [] temp2 = br.readLine().split(" ");
	for(int j=0; j<width; j++) {
	map[i][j] = Integer.parseInt(temp2[j]);
	}
	}
	int area;
	int time = 0;
	while(true){
	area = 0;
	visited = new boolean[height][width];
	// 녹이기
	for(int i=0; i<height; i++){
	for(int j=0; j<width; j++){
	if(map[i][j] != 0 && !visited[i][j]) {
	dfs(i,j);
	area++;
	}
	}
	}
	if(area == 0) {
	bw.write("" + 0);
	break;
	}
	if(area >= 2) {
	bw.write("" + time);
	break;
	}
	time++;
	}
	bw.flush();
	bw.close();
	br.close();
	}
	public static void dfs(int x, int y) {
	// 위, 아래, 왼쪽, 오른쪽
	int[] xdir = {-1,1,0,0};
	int[] ydir = {0,0,-1,1};
	Stack<Node> stack = new Stack<>();
	ArrayList<Node> list = new ArrayList<>();
	stack.add(new Node(x,y));
	while(!stack.isEmpty()) {
	Node n = stack.pop();
	int a = n.a;
	int b = n.b;
	int ax, ay;
	int seaNum = 0;
	visited[a][b] = true;
	// 4방향 보기
	for(int i=0; i<4; i++) {
	ax = n.a + xdir[i];
	ay = n.b + ydir[i];
	// 범위를 넘지 않는지 확인
	if(isCorrect(ax, ay)) {
	// 빙산은 stack에 넣고 탐색
	if(map[ax][ay] != 0){
	if(!visited[ax][ay]){
	stack.add(new Node(ax, ay));
	}
	}
	else {
	// 빙산에 연결된 바다 수 check
	seaNum++;
	}
	}
	}
	int k = map[a][b] - seaNum > 0 ? map[a][b] - seaNum : 0;
	list.add(new Node(a, b, k));
	}
	for(Node n: list) {
	map[n.a][n.b] = n.seaNum;
	}
	}
	public static boolean isCorrect(int x, int y) {
	boolean flag = true;
	if(x < 0 || x >= height || y < 0 || y >= width)
	flag = false;
	return flag;
	}
	}

view raw BOJ2573_빙산.java hosted with ❤ by GitHub