[백준] 빙산(BFS)

BFS 문제였다.

어려운 것은 얼음 녹는건 구현에 성공 했는데 얼음 덩어리를 어떻게 파악할 수 있지? 였다..

덩어리를 파악하는 방법은, 2차원 배열을 계속 탐색하다가 0이 아닌 수가 나오면 그 주변 값(동서남북)을 계속 탐색하며 동서남북에 대해서도 덩어리가 있는지 체크하는 것이다.

방문 배열을 업데이트 해 방문한 것은 visitied[i] 를 true로 둔다.

예를 들어 위의 그림에서 0이 아닌 가장 처음 2의 주변을 탐색한다. 

2의 동서남북에 위치해있는 0,3,4,0을 탐색하고, 동서남북 중에서도 0이 아닌 수가 나오면 그 주변을 또 탐색한다. 예를 들어 3이 0이 아니므로 3의 주변을 탐색한다. 3의 주변 중에 7을 탐색한다.. -> 이런 식으로 가면 계속 인접한 빙하들을 만날 수 있다.

이렇게 큐에 계속 주변 좌표를 넣고 탐색하고, 큐가 빌때까지 탐색하면 하나의 빙하가 되는 것이다.

빙하 덩어리를 체크하는 함수

private static int countIce(){
	for(int i=0; i<N;i++){
        Arrays.fill(visited[i],false); //탐색 전, 전부 거짓으로 채운다.
    }
    int cnt = 0;
    for(int i=0; i<N;i++){
    	for(int j=0; j<M; j++){
        	if(arr[i][j] > 0 && !visited[i][j]){ //방문하지 않았거나, 0보다 크면 덩어리
            	bfs(i,j); //그것에 대해서 근처를 탐색한다.
                cnt++; //하나의 덩어리가 된다.
            }
        
        }
    }
    return cnt;
}

빙하 덩어리를 BFS로 체크하는 함수(Deque 사용)

private static void bfs(int x, int y){ //인덱스들
	Deque<int []> dq = new ArraysDeque<>();
    dq.add(new int[]{x,y})
    visited[x][y] = true;
    while(!dq.isEmpty()){
    	int [] current = dq.poll();
        int cx = current[0];
        int cy = current[1]; 
        for(int i=0; i<4;i++){
        	int nx = cx + dx[i];
            int ny = cy + dy[i];
        	if(isValid(nx,ny) && !visitied[nx][ny] && arr[nx][ny] > 0){ //덩어리면
            	visited[nx][ny] = true; //방문 처리
                dq.offer(new int[]{nx,ny}); //덩어리 주변도 다시 탐색
            }
        }
    }
}

빙하를 녹이는 함수

private static void meltIce(){
	int [][] temp = new int [N][M]; //1년 뒤에 업데이트가 되어야 하므로, 기존 배열에 영향을 미치지 않도록 tmp 배열을 만든다.
    for(int i=0; i<N; i++){
    	for(int j=0; j<M;j++){
        	int ice = arr[i][j];
            int count = 0; //0의 개수(이만큼 녹여야 하므로)
            for(int move = 0; move<4; move++){
            	int nr = i + dx[move]; //벡터 배열
                int nc = j + dy[move]; 
                
                if(isValid(nr,nc) && arr[nr][nc] ==0){
                	count++; //0인 것이 나오면 세준다.
                }
      
            }
            ice -= count;
            temp[i][j] = Math.max(ice,0); //녹이는 과정. 빙하는 0 이하로 내려가지 않는다.
        }
    }
    arr = temp; //마지막에 1년 뒤의 빙하로 교체한다.

}

 

BFS는 템플릿이 참 중요한 것 같다! 벡터 방향 배열과 방문 배열 등을 정의하고 풀면 패턴은 비슷하다. 빙하 문제는 bfs를 두개 써야하는 문제였다..