본문 바로가기
[백준]

[BaekJoon/백준] 2636번 치즈

by Hevton 2022. 6. 24.
반응형

 

그렇게 깔끔하게 풀진 못해서 조금 아쉽다.

그리고 나는 DFS를 썼는데, 다른분들의 코드를 보니 BFS로 푸는 방법이 더 효율적일 것 같다.

 

SIDE 부분을 Queue에 넣어준 뒤, 그것들의 인접정보를 이용해서 점점 줄여나가는.. BFS 문제.

#include <iostream>
#include <cstring>

using namespace std;

int N, M;

int ARR[100][100];
bool VISIT[100][100];

int SIDE = 2;

int mx[4] = {-1, 1, 0, 0};
int my[4] = {0, 0, -1, 1};

int FLIP_COUNT;
int BACKUP;

void dfs(int x, int y) {
    
    int xx, yy;
    
    VISIT[x][y] = true;
    
    if(ARR[x][y] == 1) {
        ARR[x][y] = SIDE;
        FLIP_COUNT++;
        return;
    }
    
    for(int i = 0; i < 4; i++) {
        
        xx = x + mx[i];
        yy = y + my[i];
        
        if(xx < 0 || xx >= N || yy < 0 || yy >= M)
            continue;
        
        if(!VISIT[xx][yy])
            dfs(xx, yy);
    }
    
}

int main() {
    
    cin >> N >> M;
    
    
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            cin >> ARR[i][j];
        }
    }
    
    
    do {
        BACKUP = FLIP_COUNT;
        FLIP_COUNT = 0;
        dfs(0, 0);
        SIDE++;
        memset(VISIT, 0, sizeof(VISIT));

    } while(FLIP_COUNT > 0);
    
    
    cout << SIDE - 3 << "\n" << BACKUP << "\n";
    
}

 

반응형