백준 2573 빙산

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

해당 문제는 의외로 간단하다.

dfs 탐색을 해주고 녹아야되는 빙산 체크 + 얼마큼 녹아야되는지 설정해주고 필자는 stack에 저장

전체에 대해 dfs 탐색을 진행하고 2번을 진행할수있다면 2덩이 분리체크

혹은 모두 녹아버린 경우를 체크하면서 무한 while문을 돌리면된다.

0. 무한 while문 안에서 돌린다.
1. 전체에 대해 dfs 탐색
2. 빙산이 녹는 경우는 stack 에 저장
3. 두덩이 기저조건 혹은 모두 녹았는지 확인
4. 기저조건이 아니라면 stack 에서 꺼내 빙산을 녹이고 다시 while문으로

코드는 다음과같다

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


class melt{
	int x;
	int y;
	int m;
	
	public melt(int x, int y, int m) {
		this.x=x;
		this.y=y;
		this.m=m;
	}
}

public class 빙산 {

	static int lx;
	static int ly;
	static int[][] array;
	static boolean[][] visited;
	static Stack<melt> s;
	static int[] dx = new int[] {0,0,1,-1};
	static int[] dy = new int[] {1,-1,0,0};
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		lx = Integer.parseInt(st.nextToken());
		ly = Integer.parseInt(st.nextToken());
		
		array = new int[lx][ly];
		for(int i=0;i<lx;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<ly;j++) {
				array[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		int answer = 0;
		while(true) {
			
			visited = new boolean[lx][ly];
			s= new Stack<>();
			int meltc = 0;
			
			for(int i=0;i<lx;i++) {
				for(int j=0;j<ly;j++) {
					if(array[i][j]!=0 && !visited[i][j]) {
						meltc++;
						visited[i][j] = true;
						dfs(i,j);
					}
				}
			}
			
			
			//기저조건
			if(meltc>=2) {
				break;
			}
			
			if(s.isEmpty()) {
				answer= 0;
				break;
			}
			
			
			while(!s.isEmpty()) { //녹는과정
				melt cur = s.pop();
				
				array[cur.x][cur.y] = array[cur.x][cur.y]-cur.m;
				
				if(array[cur.x][cur.y]<0) array[cur.x][cur.y]=0;
			}
			//1년지낫어욤
			answer++;
		}
		
		System.out.println(answer);
	}
	
	public static boolean endcheck() {
	
		return true;	
	}
	
	public static void dfs(int x, int y) {
		
		int zerocount = 0;
		for(int i=0;i<4;i++) {
			
			int nx = x+dx[i];
			int ny = y+dy[i];
			
			if(nx<0 || nx>=lx || ny<0|| ny>=ly) continue;
			
			if(array[nx][ny]==0) zerocount++;
			else {
				if(!visited[nx][ny]) {
					visited[nx][ny] = true;
					dfs(nx,ny);
				}
			}
			
		}
		
		if(zerocount!=0) {
		s.add(new melt(x,y,zerocount));
		}
	
	
	}
	

}

기저조건 체크를 잘못해서 한번 시간초과가 났다 ㅎㅎ.. 얼른 골드3으로 ㄱㄱ