BOJ2573 빙산*

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

2573번: 빙산

 

맵이외에 얼음을 따로 관리 해주어서 시간복잡도를 줄일 수 있다.

문제에서 얼음칸의 수를 제한시켜주기 때문에(이런게 힌트인 경우가 있다.) 가능

 

리스트에서 원소를 삭제할 때 순서가 상관없다면 맨뒤에 것을 해당 인덱스에 집어넣고 맨뒤에 거를 지우면(맨뒤는 O(1)) 시간복잡도를 낮출 수 있다.

 

import java.util.*;
import java.io.*;
public class Main
{
    
    static int[][] map;
    static boolean[][] visited;
    static int n;
    static int m;
    static int[][] move = {{1,0},{0,1},{-1,0},{0,-1}};
    public static boolean bfs(int start_x , int start_y){
        Queue<int[]> q = new LinkedList();
        
        q.offer(new int[]{start_x,start_y});
        boolean check =false;
        while(q.size()>0){
            int[] now = q.poll();   
            int now_x = now[0];
            int now_y = now[1];

            if(visited[now_x][now_y] || map[now_x][now_y]==0) continue;
            check=true;
            visited[now_x][now_y] = true;
            for(int[] mo :move){
                if(now_x+mo[0] >=0 && now_x+mo[0] <= (n-1) && now_y+mo[1] >=0 && now_y+mo[1] <= (m-1)){
                    if(!visited[now_x+mo[0]][now_y+mo[1]] && map[now_x+mo[0]][now_y+mo[1]] != 0){
                        q.offer(new int[]{now_x+mo[0],now_y+mo[1]});
                    }
                }
            }
                    
  
        }
        return check;
    }
    
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] input= br.readLine().split(" ");
		n = Integer.parseInt(input[0]);
		m = Integer.parseInt(input[1]);
		
		map = new int[n][m];
		
		
		for(int i=0; i< n;i++){
		    String[] temp = br.readLine().split(" ");
		    for(int j=0;j<m;j++){
		        map[i][j]=Integer.parseInt(temp[j]);
		    }
		}
		
		
		int year=0;
		while(true){
		    

		    int ans =0;
		    
		    visited = new boolean[n][m];
		    
		    // 얼음 덩어리 세기
		    for(int j=1;j<n;j++ ){
		        for(int k=1;k<m;k++){
		            if(bfs(j,k)) ans++;
		        }
		    }

		    if(ans==0){
		        System.out.println(0);
		        return;
		    }
		    if(ans>1){
		        System.out.println(year);
	            return;
		    }
		    
		    
	        //1년 지남 , 얼음 녹이기	    
		    year++;
            
            
            int[][] newmap= new int[n][m];
		    for(int j=0;j<n;j++){
		        for(int k=0;k<m;k++){
		            int count=0;
		            for(int[] mo :move){
		                if(j+mo[0] >=0 && j+mo[0] <= (n-1) && k+mo[1] >=0 && k+mo[1] <= (m-1)){
		                    if (map[j+mo[0]][k+mo[1]]==0){
		                    count++;
		                    }    
		                }
		            }
		            newmap[j][k]=Math.max(0, map[j][k]-count);
		            
		        }
		    }
		    map = newmap;
		    
		  //  for(int[] x: map){
		  //      for(int d :x){
		  //          System.out.print(d+" ");
		            
		  //      }
		  //      System.out.println();
		  //  }
		    
		  //  System.out.println();
		    
		    
		} 
    
	}
	
		
		
		
		
	
}

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    static int n, m;
    static int[][] earth;
    static boolean[][] visited;
    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1 ,1};
    static List<Ice> iceList = new ArrayList<>();
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();

        earth = new int[n][m];
        visited = new boolean[n][m];
        iceList = new ArrayList<>();

        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                earth[i][j] = sc.nextInt();
                if(earth[i][j] > 0) {
                    iceList.add(new Ice(i, j, earth[i][j]));
                }
                // iceList에 있는 빙산들의 좌표를 방문처리
                visited[i][j] = true;
            }
        }
        for(int year = 1; !iceList.isEmpty(); year++) {
            // 빙산 녹이기
            for(int i = 0; i < iceList.size(); i++) {
                Ice ice = iceList.get(i);
                for(int j = 0; j < 4; j++) {
                    int nr = ice.row + dr[j];
                    int nc = ice.col + dc[j];
                    if(earth[nr][nc] == 0) ice.height--;
                }
            }

            // 빙산 녹은 후 높이 갱신
            for(int i = 0; i < iceList.size(); i++) {
                Ice ice = iceList.get(i);
                if(ice.height <= 0) {
                    earth[ice.row][ice.col] = 0;
                    iceList.set(i, iceList.get(iceList.size()-1));
                    iceList.remove(iceList.size()-1);
                    i--;
                }
                // DFS 탐색 대상 -> visited 초기화
                else {
                    visited[ice.row][ice.col] = false;
                }
            }

            // iceList 첫번째 빙산이 몇개와 연결되어있는지 카운트
            // 모든 빙산의 개수와, 첫번째 빙산과 연결된 빙산의 개수가 다르면 빙산이 분리되었다는 뜻
            if(iceList.size() > 0 && dfs(iceList.get(0).row, iceList.get(0).col) != iceList.size()) {
                System.out.println(year);
                System.exit(0);
            }
        }
        System.out.println(0);
    }
    static int dfs(int r, int c) {
        visited[r][c] = true;
        int cnt = 1;
        for(int i = 0; i < 4; i++) {
            int nr = r + dr[i];
            int nc = c + dc[i];
            if(visited[nr][nc]) continue;
            cnt += dfs(nr, nc);
        }
        return cnt;
    }
}

class Ice {
    int row;
    int col;
    int height;
    public Ice(int r, int c, int h) {
        this.row = r;
        this.col = c;
        this.height = h;
    }
}