[백준] 2573 빙산 - BFS + 구현 JAVA

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

2573번: 빙산

문제풀이

BFS 문제에 구현문제였습니다.

 

문제 푸는 방식은

1. 얼음덩어리가 몇개인지 구합니다. (저는 BFS를 통해 구했습니다.)

2. 얼음덩어리가 1개라면, BFS를 통해서 해당 얼음들을 마주친 바다의 면의 개수만큼 녹여줍니다.

조건 :

-얼음덩어리가 2개 이상이라면 정답을 출력합니다.

-얼음덩어리가 1개로 끝난다면 0 을 출력합니다. 

위 2가지대로 생각하면 풀 수 있는 문제입니다.

 

여기서 실수했던점은,

1. 얼음 덩어리는 모두 같이 녹는다. ( 얼음덩어리를 녹일때, 한번에 다 같이 녹여야 계산값이 영향받지 않습니다. )

2. 얼음덩어리가 한덩어리로 모두 녹아내린다면,  0을 출력합니다.

첫번쨰 조건은 생각하고 코딩했지만, 코딩하다가 보니 까먹어서 놓쳤습니다.

문제를 처음에 세팅할떄 주석을 남기거나 생각을 정리하고 진행해야할것 같습니다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {


	public static int N,M;
	public static int[][] map;
	public static Queue<Node> q = new LinkedList<>();
	public static HashSet<Node> hashset = new HashSet<>();
	public static boolean[][] visited;
	public static int result = 0;
	public static int[][] tempMap;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	M = Integer.parseInt(st.nextToken());
    	
    	map = new int[N][M];
    	visited = new boolean[N][M];
    	tempMap = new int[N][M];
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		for(int j=0;j<M;j++) {
    			map[i][j] = Integer.parseInt(st.nextToken());
    		}
    	}
    	
    	int ice_cnt = 0;
    	while(ice_cnt < 2) {
    		visited = new boolean[N][M];
    		tempMap = new int[N][M];
    		q.clear();
    		
	//    	먼저 빙산이 2개로 떨어져있는지 확인합니다.
	    	ice_cnt = 0;
	    	boolean meltflag = false;
            
            //얼음덩어리가 몇개인지 CalculateCnt(), BFS를 통해 알아냅니다.
	    	for(int i=0;i<N;i++) {
	    		for(int j=0;j<M;j++) {
	    			if(map[i][j] > 0 && visited[i][j] == false) {
	    				q.offer(new Node(i, j, 0));
	    				visited[i][j] = true;
	    				CalculateCnt();
	    				ice_cnt += 1;
	    				meltflag = true;	    				
	    			}
	    		}
	    	} 
            //만약 얼음덩어리가 한개도 없다면, 얼음덩어리가 1개인상태로 끝난것이므로 0이고, 종료시킵니다.
	    	if(meltflag == false) {
	    		result = 0;
	    		break;
	    	}
            //만약 얼음덩어리가 2개로 나눠지면 종료됩니다.
	    	if(ice_cnt >= 2) break;
	    	
	    	
	    	q.clear();
	    	//빙산을 녹이기 위해 빙산의 정보를 찾습니다.
	    	for(int i=0;i<N;i++) {
	    		for(int j=0;j<M;j++) {
	    			if(map[i][j] > 0) {
	    				q.offer(new Node(i, j, 0));
	    			}
	    		}
	    	}    	
            //BFS를 통해 hashset에 Node정보(x,y) 를 넣습니다.    	
	    	BFS();
	    	result+=1;
	    	
    	}
    	System.out.println(result);

    }
    
    public static void CalculateCnt() {
    	int[] dx = {-1,1,0,0};
    	int[] dy = {0,0,-1,1};
    	while(!q.isEmpty()) {
    		Node temp = q.poll();
    		int x = temp.x;
    		int y = temp.y;
    		int cnt = temp.cnt;
    		for(int dir=0;dir<4;dir++) {
    			int nx = x + dx[dir];
    			int ny = y + dy[dir];
    			if( nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
    			if(map[nx][ny] == 0) continue;
    			if(visited[nx][ny] == true) continue;
    			q.offer(new Node(nx, ny, 0));
    			visited[nx][ny] = true;
    		}
    	}
    }
    
    
    //얼음을 실제로 녹입니다.
    public static void BFS() {
    	int[] dx = {-1,1,0,0};
    	int[] dy = {0,0,-1,1};
    	while(!q.isEmpty()) {
    		Node temp = q.poll();
    		int x = temp.x;
    		int y = temp.y;
    		int cnt = temp.cnt;
    		for(int dir=0;dir<4;dir++) {
    			int nx = x + dx[dir];
    			int ny = y + dy[dir];
    			if( nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
    			if(map[nx][ny] == 0) cnt++;
    		}
    		tempMap[x][y] = cnt;
    	}
    	
    	for(int i=0;i<N;i++) {
    		for(int j=0;j<M;j++) {
    			map[i][j] -= tempMap[i][j];
    			if(map[i][j] < 0) map[i][j] = 0;
    		}
    	}
    }
    
}

class Node{
	int x;
	int y;
	int cnt;
	public Node(int x, int y, int cnt) {
		this.x=x;
		this.y=y;
		this.cnt=cnt;
	}
}