[C++] 백준 2573 빙산 - 테스트 케이스

 

 

 

지도 유형 BFS 레퍼런스를 변형하여 해결하였습니다.

 

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <queue>
#include <string.h>
#define MAX_SIZE 301
using namespace std;

int n, m;
int cnt = 0, year = 0;   // 덩어리 수, 지난 년도
int map[MAX_SIZE][MAX_SIZE];

int map2[MAX_SIZE][MAX_SIZE];
bool visited[MAX_SIZE][MAX_SIZE];

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

void BFS(int x, int y){
    queue< pair<int, int> > q;
    q.push(make_pair(x, y));
    
    visited[x][y] = true;
    
    while(!q.empty()){
        x = q.front().first;
        y = q.front().second;
        q.pop();
        
        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if(nx >= 0 && nx < n && ny >= 0 && ny < m){
                if(map2[nx][ny] > 0 && visited[nx][ny] == false){
                    
                    visited[nx][ny] = true;
                    q.push(make_pair(nx, ny));
                }
            }
            
        }
    }
}

void print_array(int arr[][MAX_SIZE]){
    printf("\n");
    
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            printf("%d ", arr[i][j]);
        }
        printf("\n");
    }
}

int main(void) {
    
    scanf("%d%d", &n, &m);
    
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            scanf("%d", &map[i][j]);
        }
    }
    
    memcpy(map2, map, sizeof(map));
    
    // 덩어리 개수 세기
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(map2[i][j] > 0 && visited[i][j] == false){

                BFS(i, j);
                cnt++;
            }
        }
    }
    
    // 처음부터 2 이상인지, 0인지 확인
    if(cnt >= 2 || cnt == 0){
        printf("0\n");
        return 0;
    }

    
    while(cnt < 2){
        cnt = 0;
        memset(visited, false, sizeof(visited));
        
        int mx, my;
        // 1 이상인 숫자 주위 체크해서 1 감소시키기
        for(int i=0; i<(n); i++){
            for(int j=0; j<(m); j++){
                if(map[i][j] > 0){
                    for(int k=0; k<4; k++){
                        mx = i + dx[k];
                        my = j + dy[k];

                        if(mx >= 0 && mx <n && my >= 0 && my < m){
                            if(map[mx][my] == 0 && map2[i][j] > 0){
                                map2[i][j]--;
                            }
                        }
                    }
                }
            }
        }

        // 덩어리 개수 세기
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(map2[i][j] > 0 && visited[i][j] == false){

                    BFS(i, j);
                    cnt++;
                }
            }
        }
        
//        print_array(map);
//        print_array(map2);
        
        if(cnt == 0){
            printf("0\n");
            return 0;
        }
        
        year++;
        
        memcpy(map, map2, sizeof(map2));
    }
    
    printf("%d\n", year);
    

    return 0;
}

 

 

 

 

 

 

 

5 7
0 0 0 0 0 0 0
0 3 6 0 6 7 0
0 3 0 0 0 10 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0

정답 0

 

5 5
0 0 0 0 0
0 0 10 10 0
0 10 0 10 0
0 0 10 10 0
0 0 0 0 0

정답 0

 

 

5 5
0 0 0 0 0
0 2 2 2 0
0 2 2 2 0
0 2 2 2 0
0 0 0 0 0

정답 0

 

 

7 7
0 0 0 0 0 0 0
0 9 9 9 9 9 0
0 9 0 1 0 9 0
0 9 0 9 0 9 0
0 9 0 0 0 9 0
0 9 9 9 9 9 0
0 0 0 0 0 0 0

정답 1

 

 

 

5 5
0 0 0 0 0
0 0 9 0 0
0 0 3 1 0
0 0 9 0 0
0 0 0 0 0

정답 2

 

 

 

5 7
0 0 0 0 0 0 0
0 3 3 2 3 3 0
0 4 0 4 0 3 0
0 0 0 0 4 3 0
0 0 0 0 0 0 0

정답 0

 

 

 

5 7
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 10 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0

정답 0

 

 

5 7
0 0 0 0 0 0 0
0 3 3 1 3 3 0
0 4 0 4 0 3 0
0 0 0 0 4 3 0
0 0 0 0 0 0 0

정답 1

 

 

 

 

 

5 7
0 0 0 0 0 0 0
0 3 6 3 6 7 0
0 3 0 0 0 10 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0

정답 2

 

 

 

 

5 7
0 0 0 0 0 0 0
0 3 6 0 6 7 0
0 3 0 0 0 10 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0

정답 0

 

 

5 7
0 0 0 0 0 0 0
0 9 8 9 8 9 0
0 9 8 9 8 9 0
0 9 8 9 8 9 0
0 0 0 0 0 0 0

정답 0

 

 

 

5 7
0 0 0 0 0 0 0
0 9 8 3 8 9 0
0 9 8 0 8 9 0
0 9 8 9 8 9 0
0 0 0 0 0 0 0

정답 5

 

 

 

 

5 5
0 0 0 0 0
0 1 0 1 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

정답 0

 

 

 

 

고뇌의 흔적들...

 

 

 

 

오늘 알게된 것 & 교훈

 

1. return 1;은 런타임 에러를 발생시킨다.

2. 문제를 잘 읽자, 안되면 문제를 천천히 다시 읽자.

3. 중간 결과를 출력해서 확인해보자.