큰돌님 4-H 질문 있습니다.

작성한 질문수 5

0

안녕하세요 민규님 ㅎㅎ

BFS를 하신건 괜찮습니다. 단, 한번의 BFS로 가능할 것 같습니다. visited1, 2, ... 가 많은 것은 room 배열을 기반으로 최적화할 수도 있을 것 같습니다.

제가 한번 다듬어봤는데 이렇게 해보시겠어요?

#include <bits/stdc++.h>
using namespace std;

const int MAX_ROW = 54;
const int MAX_COL = 54;
int castle[MAX_ROW][MAX_COL];
int room[MAX_ROW][MAX_COL];
int roomSize[2504];
int n, m;
const int dy[4] = {0, -1, 0, 1};
const int dx[4] = {-1, 0, 1, 0};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n >> m;
    for (int i = 0; i < m; i++){
        for (int j = 0; j < n; j++){
            cin >> castle[i][j];
        }
    }
    
    int roomCount = 0;
    int maxRoomArea = 0;
    
    for (int i = 0; i < m; i++){
        for (int j = 0; j < n; j++){
            if (room[i][j] == 0) {
                roomCount++;
                int area = 0;
                queue<pair<int,int>> q;
                q.push({i, j});
                room[i][j] = roomCount;
                
                while (!q.empty()){
                    auto [y, x] = q.front();
                    q.pop();
                    area++;
                    
                    for (int d = 0; d < 4; d++){
                        int ny = y + dy[d];
                        int nx = x + dx[d];
                        if (ny < 0 || nx < 0 || ny >= m || nx >= n || room[ny][nx] != 0)
                            continue;
                        if (castle[y][x] & (1 << d))
                            continue;
                        room[ny][nx] = roomCount;
                        q.push({ny, nx});
                    }
                }
                roomSize[roomCount] = area;
                maxRoomArea = max(maxRoomArea, area);
            }
        }
    }
    
    int biggest = 0;
    for (int i = 0; i < m; i++){
        for (int j = 0; j < n; j++){
            for (int d = 0; d < 4; d++){
                int ny = i + dy[d], nx = j + dx[d];
                if(ny < 0 || nx < 0 || ny >= m || nx >= n)
                    continue;
                if (room[i][j] != room[ny][nx])
                    biggest = max(biggest, roomSize[room[i][j]] + roomSize[room[ny][nx]]);
            }
        }
    }
    
    cout << roomCount << "\n" << maxRoomArea << "\n" << biggest;
    return 0;
}

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.