(JAVA) [BOJ]백준 2573번, 빙산

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

2573번: 빙산

2573, 빙산

[ 난이도 : 골드 4 ]

이번 문제는 BFS & DFS, 그래프 이론을 사용해서 풀어보겠다.

 

# Process

input

: 입력받은 값들을 기반으로 area 배열에 값을 넣어주는 것으로 시작한다.

static void input() 
{
    N = scan.nextInt();
    M = scan.nextInt();
    area = new int[N][M];

    for(int i=0;i<N;i++)
    {
        for(int j=0;j<M;j++)
        {
            area[i][j] = scan.nextInt();
        }
    }
}

 

 

빙산의 개수 카운트

: 우선적으로 빙산의 개수를 세어줘야 한다. 빙산의 개수가 2 이상이 되는 경우 루프를 종료하고 녹이는

작업을 진행한 횟수를 출력해 주어야 한다.

 

빙산의 개수를 세는 과정은 dfs 사용하였다. dfs 를 호출하는 수 반환해주는 iceCount() 를 계속 호출해준다.

static void pro() 
{
    int cnt = 0;
    int ans = 0;

    // 빙산의 개수가 2개 이상이 될 때 까지 녹이는 작업을 반복
    while((cnt = iceCount()) < 2)
    {
        // 전부다 녹은 경우
        if(cnt == 0)
        {
            ans = 0;
            break;
        }

        // 빙산을 녹이는 BFS
        bfs();
        ans++;
    }

    System.out.println(ans);
}

// 빙산의 갯수를 카운트
    static int iceCount()
    {
        visit = new boolean[N][M];

        int cnt = 0;
        for(int i=0;i<N;i++)
        {
            for(int j=0;j<M;j++)
            {
                if(area[i][j] != 0 && !visit[i][j])
                {
                    // 호출될 때마다 빙산의 개수 + 1
                    dfs(i,j);
                    cnt++;
                }
            }
        }

        return cnt;
    }

 

빙산을 녹이자

: 빙산의 개수를 세어줬으면 녹이는 작업도 진행해 주어야 한다. 빙산을 녹이는 작업은 BFS 를 사용하였다.

전체를 순회하며 0이 아닌 지역의 x,y 좌표를 모두 큐에 넣어주고 4분면을 비교하며 그 수를 빼주는 과정을 반복한다.

 

여기서 주목해야 할 것이 방문여부이다. 

시간이 지남에 따라 전체 빙하의 높이가 1이 줄어야 하는데 순차적으로 진행하다보니 먼저 0이 되고

그 다음 순서에서 인접한 부분을 0으로 간주하여 -2가 되는 경우가 발생할 수 있기 때문이다.

static void bfs() 
{
    Queue<Integer> Q = new LinkedList<>();

    boolean[][] visit = new boolean[N][M];

    for(int i=0;i<N;i++)
    {
        for(int j=0;j<M;j++)
        {
            if(area[i][j] != 0)
            {
                visit[i][j] = true;
                Q.add(i);
                Q.add(j);
            }
        }
    }

    while(!Q.isEmpty())
    {
        int x = Q.poll();
        int y = Q.poll();

        int minusNum = 0;

        for(int k=0;k<4;k++)
        {
            int nx = x + dir[k][0];
            int ny = y + dir[k][1];

            // 범위에 대한 예외처리
            if(nx<0 || ny<0 || nx>=N || ny>= M) continue;
            // 먼저 녹아서 0이 되는 경우를 방지
            if(visit[nx][ny]) continue;
            // 바닷물과 인접해 있는 경우
            if(area[nx][ny] == 0) minusNum++;
        }

        if(area[x][y] - minusNum < 0)
            area[x][y] = 0;
        else
            area[x][y] -= minusNum;
    }
}

 

전체 코드

: 위의 긴 과정을 통한 전체 코드이다.

static int[][] dir = {{1,0},{-1,0},{0,1},{0,-1}};
static int N, M;
static int[][] area;
static boolean[][] visit;

static void input() 
{
    N = scan.nextInt();
    M = scan.nextInt();
    area = new int[N][M];

    for(int i=0;i<N;i++)
    {
        for(int j=0;j<M;j++)
        {
            area[i][j] = scan.nextInt();
        }
    }
}

static void pro() 
{
    int cnt = 0;
    int ans = 0;

    // 빙산의 개수가 2개 이상이 될 때 까지 녹이는 작업을 반복
    while((cnt = iceCount()) < 2)
    {
        // 전부다 녹은 경우
        if(cnt == 0)
        {
            ans = 0;
            break;
        }

        // 빙산을 녹이는 BFS
        bfs();
        ans++;
    }

    System.out.println(ans);
}

// 빙산의 갯수를 카운트
static int iceCount()
{
    visit = new boolean[N][M];

    int cnt = 0;
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<M;j++)
        {
            if(area[i][j] != 0 && !visit[i][j])
            {
                // 호출될 때마다 빙산의 개수 + 1
                dfs(i,j);
                cnt++;
            }
        }
    }

    return cnt;
}

// DFS
static void dfs(int x, int y) 
{
    visit[x][y] = true;

    for(int k=0;k<4;k++)
    {
        int nx = x + dir[k][0];
        int ny = y + dir[k][1];

        if(nx<0 || ny<0 || nx>=N || ny>= M) continue;
        if(visit[nx][ny]) continue;
        if(area[nx][ny] == 0) continue;

        dfs(nx, ny);
    }
}

static void bfs() 
{
    Queue<Integer> Q = new LinkedList<>();

    boolean[][] visit = new boolean[N][M];

    for(int i=0;i<N;i++)
    {
        for(int j=0;j<M;j++)
        {
            if(area[i][j] != 0)
            {
                visit[i][j] = true;
                Q.add(i);
                Q.add(j);
            }
        }
    }

    while(!Q.isEmpty())
    {
        int x = Q.poll();
        int y = Q.poll();

        int minusNum = 0;

        for(int k=0;k<4;k++)
        {
            int nx = x + dir[k][0];
            int ny = y + dir[k][1];

            // 범위에 대한 예외처리
            if(nx<0 || ny<0 || nx>=N || ny>= M) continue;
            // 먼저 녹아서 0이 되는 경우를 방지
            if(visit[nx][ny]) continue;
            // 바닷물과 인접해 있는 경우
            if(area[nx][ny] == 0) minusNum++;
        }

        if(area[x][y] - minusNum < 0)
            area[x][y] = 0;
        else
            area[x][y] -= minusNum;
    }
}

public static void main(String[] args) 
{
    input();
    pro();
}