[비트마스킹][bfs] 2234 성곽 c++구현

목차

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

문제

 

문제 구현 방향

비트 마스킹을 통해 bfs로 탐색하는 식으로 풀었다. 

꼭 bfs가 아니어도 dfs로도 풀 수 있다.

 

 

문제 구현 시 주의점

이차원 배열에서는 아래쪽이 북쪽 방향이니 주의해야 한다.

감이 안잡힌다면 일단 완전탐색이 최고인 것 같다.

 

코드 구현

#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<math.h>
#include<map>

using namespace std;

//주의 이차원 배열은 아래쪽이 북쪽 방향
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, -1, 0, 1 };
int M, N;
int board[51][51] = { 0 };
int visit[51][51] = { 0 };
int cnt = 0;
int maxS = 0;
void bfs(int startX, int startY, int cnt) {
    int s = 1;
    queue<pair<int, int>> q;
    q.push({ startX, startY });
    visit[startY][startX] = cnt;
    while (!q.empty()) {
        int x = q.front().first;
        int 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 > M - 1 || ny < 0 || ny > N - 1)
                continue;
            if (board[y][x] & (1 << i)) 
                continue;

            if (visit[ny][nx])
                continue;
            
         
            q.push({ nx, ny });
            visit[ny][nx] = cnt;
            s++;
        }
    }
    maxS = max(maxS, s);
}

int main() {
    cin >> M >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> board[i][j];
        }
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (!visit[i][j])
            {
                cnt++;
                bfs(j, i, cnt);
            }
        }
    }
    cout << cnt << "\n";
    cout << maxS << "\n";
    maxS = 0;
   
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            for (int p = 0; p < 4; p++) {
                if (board[i][j] & (1 << p)) {
                    board[i][j] &= ~(1 << p);
                    fill(&visit[0][0], &visit[0][0] + 51 * 51, 0);
                    bfs(j, i, 1);
                    board[i][j] |= (1 << p);
                }

            }
        }
    }
    cout << maxS;

  
    return 0;
}

 

 

캐싱을 이용한 코드 구현 방법

위의 코드는 5중 반복문이기 때문에 매우 비효율적이다. 따라서 사이즈를 저장해놓고 인접할 경우 사이즈를 합쳐 최대인 값을 구하는 방식으로 다시 구현해보았다.

#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<math.h>
#include<map>

using namespace std;

//주의 이차원 배열은 아래쪽이 북쪽 방향
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, -1, 0, 1 };
int M, N;
int board[51][51] = { 0 };
int visit[51][51] = { 0 };

//새로 추가한 size배열
int sizeArray[100] = { 0 };

int cnt = 0;
int maxS = 0;

void bfs(int startX, int startY, int cnt) {
    int s = 1;
    queue<pair<int, int>> q;
    q.push({ startX, startY });
    visit[startY][startX] = cnt;
    while (!q.empty()) {
        int x = q.front().first;
        int 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 > M - 1 || ny < 0 || ny > N - 1)
                continue;
            if (board[y][x] & (1 << i)) 
                continue;

            if (visit[ny][nx])
                continue;
            
         
            q.push({ nx, ny });
            visit[ny][nx] = cnt;
            s++;
        }
    }
    sizeArray[cnt] = s;   //영역별로 사이즈 저장
    maxS = max(maxS, s);
}

int main() {
    cin >> M >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> board[i][j];
        }
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (!visit[i][j])
            {
                cnt++;
                bfs(j, i, cnt);
            }
        }
    }
    cout << cnt << "\n";
    cout << maxS << "\n";
    maxS = 0;
   
   //인접할 경우 사이즈 합치기
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (i + 1 < N) {  //인덱스 초과 여부 검사!!
                int a = visit[i][j];
                int b = visit[i + 1][j];
                if (a !=b) {
                    maxS = max(maxS, sizeArray[a] + sizeArray[b]);
                }
            }
            if (j + 1 < M) {   //인덱스 초과 여부 검사!!
                int a = visit[i][j];
                int b = visit[i][j+1];
                if (a != b) {
                    maxS = max(maxS, sizeArray[a] + sizeArray[b]);
                }
            }
        }
    }
    cout << maxS;

  
    return 0;
}