백준 2573; Java

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

2573번: 빙산

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

public class Main {
	static int N, M;
	static int[][] ice;
	static boolean[][] visited;
	static int[][] decrease;
	//사방위 
	static int[] row= {-1, 0, 1, 0};
	static int[] col= {0, 1, 0, -1};
	
	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());
		N=Integer.parseInt(st.nextToken());
		M=Integer.parseInt(st.nextToken());
		
		ice=new int[N][M];//얼음 높이 
		decrease=new int[N][M];//decrease[i][j]==(i,j)주변 0의 개수 
		visited=new boolean[N][M];
		
		for(int i=0;i<N;i++) {
			st=new StringTokenizer(br.readLine());
			for(int j=0;j<M;j++) {
				ice[i][j]=Integer.parseInt(st.nextToken());
			}
		}
		
		int mass=0;//덩어리 개수 
		int year=0;
		while(true) {
			//1년의 decrease 구해줌 
			for(int i=0;i<N;i++) {
				for(int j=0;j<M;j++) {
					if(ice[i][j]!=0 && !visited[i][j]) {
						func(i, j);
						mass++;
					}
				}
			}
			
			if(mass>=2) {
				//year++;
				break;
			}
			if(mass==0) {
				year=0;
				break;
			}
			
            //얼음 높이 갱신 
			//방문, 주변 0의 개수(decrease) 초기화
			for(int i=0;i<N;i++) {
				for(int j=0;j<M;j++) {
					ice[i][j]=ice[i][j]-decrease[i][j];
					if(ice[i][j]<0)	ice[i][j]=0;
					visited[i][j]=false;
					decrease[i][j]=0;
				}
			}	
			year++;
			mass=0;
		}
		System.out.println(year);
	}
	
	//한 덩어리 
	public static void func(int r, int c) {
		int nr, nc, qr, qc;
		Queue<node> q=new LinkedList<>();
		q.offer(new node(r, c));
		visited[r][c]=true;
		node nd;
		while(!q.isEmpty()) {
			nd=q.poll();
			qr=nd.x; 
			qc=nd.y;

			for(int a=0;a<4;a++) {
				nr=qr+row[a];
				nc=qc+col[a];
				if(nr>=0&&nr<N&&nc>=0&&nc<M) {
					if(ice[nr][nc]==0) {
						decrease[qr][qc]++;
					}
					if(ice[nr][nc]!=0 && !visited[nr][nc]) {
						q.offer(new node(nr, nc));
						visited[nr][nc]=true;
					}
				}
			}
		}
	}
}

class node {
int x;
int y;

node(int x, int y){
	this.x=x;
	this.y=y;
}
}

 

풀었다! 내가 이김v. 이 빙산아! 우하하

 

1. year 계산 어려웠음.

2. func 함수 안에서 방문을 어디 위치에서 해줘야 할지 헤맸음 <<메모리 오류 떴음 ㅜㅜ 

큐에 넣어주고 방문 표시를 꼭 해줘야지 메모리 오류가 나지 않는다.

3. 한 해가 지나고 visited, decrease 배열을 초기화해줄 때, new int[][] 혹은 new boolean[][]으로 했을 때 미친 메모리 크기를 확인할 수 있었다. 깜짝 놀랐네..

내용 3 참고