[백준] 빙산 2573 java - bfs, dfs

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

 

bfs와 dfs를 모두 활용한 문제

빙산이 분리됐는지 확인할 때에는 dfs

녹는 과정에 대한 처리는 bfs로 처리해줬다

동서남북 바다의 개수를 카운트 한 후에 빙산에서 그 값만큼 빼야하는데

이 때에 원래 빙산 상태를 어떻게 저장해야하나.. 고민하다가

빙산 상태를 매번 copy(깊은 복사) 해주었더니 시간초과가 발생했다

따라서 초반에 빙산을 모두 queue에 넣은 후에 visited 처리를 하는 방식으로

코드를 수정했다 !! (그렇다면 이후에 변화된 빙산에 영향을 받지 않고 맞닿은 바다를 계산해줄 수 있다)

 

내 풀이

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

public class Main {
    static int N, M;
    static int startX=0, startY =0;
    static int[][] graph;
    static int[][] cpyGraph;
    static boolean[][] visited;
    static boolean[][] visited2;
    static int[] dx = {0,0,1,-1};
    static int[] dy = {1,-1,0,0};

    static void dfs(int x, int y){
        cpyGraph[x][y] = graph[x][y];

        for(int i=0;i<4;i++){
            int nextX = x+dx[i];
            int nextY = y+dy[i];
            if(nextX>=0&&nextX<N && nextY>=0&&nextY<M){
                if(!visited2[nextX][nextY] && graph[nextX][nextY]!=0){
                    visited2[nextX][nextY] = true;
                    startX = nextX;
                    startY = nextY;
                    dfs(nextX, nextY);
                }
            }
        }
    }
    static void bfs(int x, int y){
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{x,y});
        visited[x][y] = true;

        while(!q.isEmpty()){
            int[] now = q.poll();
            int nowX = now[0];
            int nowY = now[1];
            int cnt = 0;
            for(int i=0;i<4;i++){
                int nextX = nowX+dx[i];
                int nextY = nowY+dy[i];
                if(nextX>=0&&nextX<N && nextY>=0&&nextY<M){
                    if(!visited[nextX][nextY]){
                        if(cpyGraph[nextX][nextY]==0)
                            cnt++;
                        else{
                            visited[nextX][nextY] = true;
                            q.add(new int[]{nextX,nextY});
                        }
                    }
                }
            }
            if(graph[nowX][nowY]>=cnt)
                graph[nowX][nowY] -= cnt;
            else
                graph[nowX][nowY] = 0;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        graph = new int[N][M];
        cpyGraph = new int[N][M];
        visited = new boolean[N][M];

        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<M;j++){
                graph[i][j] = Integer.parseInt(st.nextToken());
                cpyGraph[i][j] = graph[i][j];
            }
        }

        int year = 0;
        boolean flag = false; // 다 녹을 때까지 두 덩어리 이상으로 분리되지 않는지 판별

        while(true){
            visited = new boolean[N][M];
            visited2 = new boolean[N][M];

            int amount = 0;
            startX = 0;
            startY = 0;
            for(int i=0;i<N;i++){
                for(int j=0;j<M;j++){
                    if(graph[i][j]!=0 && !visited2[i][j]){
                        dfs(i,j);
                        amount++;
                    }
                }
            }
            if(amount>=2){
                break;
            }
            if(startX==0 && startY==0){
                flag = true;
                break;
            }

            bfs(startX, startY);

            year++;
        }

        if(flag)
            System.out.println(0);
        else
            System.out.println(year);

    }

}