[C/C++] 백준 #2573 빙산(깊이 우선 탐색)

이번 문제는 보다 좋은 알고리즘을 택하기 보다는 구현을 위주로 하였습니다.  깊이 우선 탐색은 섬의 개수가 몇개인지 판단하기 위해서 사용을 하였습니다.

 

icebergs

 

문제 링크입니다.

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

2573번: 빙산

 

문제는 빙하가 같은 높이만큼 녹을 때, 한덩어리의 빙하가 두덩어리 이상이 되는 최소 녹는 높이를 구하는 것입니다.

 

구현 자체는 간단합니다.  빙하가 녹는 높이에 따라서 빙하가 두개가 될 때의 높이를 출력하게 하였습니다.

 

제가 구현한 소스입니다.  DFS할 때 사실 녹는 높이값을 빼서 갈 수 있는 곳을 선택한다면, 굳이 배열을 여러개 사용하지 않아도 되었을텐데, 지금 보니 배열을 복잡하게 두었네요.

//------------------------------------------------
//    baekjoon #2573
//        - by Aubrey Choi
//        - created at 2019-10-30
//------------------------------------------------
#include <stdio.h>

const int d[][2]={0,1, 1,0, 0,-1, -1,0};
int dfs(char map[][300], char v[][300], int y, int x)
{
    int s=1;
    if(v[y][x]==20||map[y][x]<=0) return 0;
    v[y][x]=20;
    for(int i=0;i<4;i++) s+=dfs(map,v,y+d[i][0],x+d[i][1]);
    return s;
}
int main()
{
    int n, m, s, i, j;
    static char map[2][300][300];
    scanf("%d%d",&n,&m);
    for(i=0;i<n;i++) for(j=0;j<m;j++) { scanf("%d",&s); map[0][i][j]=s; }
    for(s=1;;s++)
    {
        int c=s&1, p=(s^1)&1, y=0, x=0, cnt=0;
        for(i=1;i<n-1;i++) for(j=1;j<m-1;j++)
        {
            map[c][i][j]=map[p][i][j];
            if(map[c][i][j]<=0) continue;
            for(int k=0;k<4;k++) if(map[p][i+d[k][0]][j+d[k][1]]<=0) map[c][i][j]--;
            if(map[c][i][j]>0) { cnt++; y=i; x=j; }
        }
        if(cnt==0) { puts("0"); break; }
        if(dfs(map[c], map[p], y, x)!=cnt) { printf("%d\n", s); break; }
    }
}