[Algorithm] Baekjoon 2234번 : 성곽

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

2234번: 성곽

struct Node
{
    int y;
    int x;
};
 
struct Room
{
    vector<Node> nodes;
};
 
bool cmp(const Room& a, const Room& b)
{
    return a.nodes.size() > b.nodes.size();
}
 
int rowSize, colSize;
bitset<4> wallInfo[50][50];
int dirs[4][2] = { {0,-1}, {-1,0},{0,1},{1,0} };
bool visited[50][50] = { false };
vector<Room> rooms;
 
bool checkInRange(int y, int x)
{
    if (y < 0 || y >= rowSize || x < 0 || x >= colSize) return false;
    return true;
}
 
void BFS(int startY, int startX, int roomsIndex)
{
    rooms[roomsIndex].nodes.push_back({ startY,startX });
 
    queue<Node> q;
    q.push({ startY,startX });
 
    while (!q.empty())
    {
        int curY = q.front().y;
        int curX = q.front().x;
        q.pop();
 
        for (int i = 0; i < 4; ++i)
        {
            int nextY = curY + dirs[i][0];
            int nextX = curX + dirs[i][1];
 
            if (!checkInRange(nextY, nextX)) continue;
            if (wallInfo[curY][curX][i] == 1) continue;
            if (visited[nextY][nextX]) continue;
 
            visited[nextY][nextX] = true;
            q.push({ nextY,nextX });
            rooms[roomsIndex].nodes.push_back({ nextY,nextX });
        }
    }
}
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
 
    cin >> colSize >> rowSize;
 
    for (int i = 0; i < rowSize; ++i)
    {
        for (int j = 0; j < colSize; ++j)
        {
            int input;
            cin >> input;
 
            wallInfo[i][j] = input;
        }
    }
 
    int roomsIndex = -1;
    for (int i = 0; i < rowSize; ++i)
    {
        for (int j = 0; j < colSize; ++j)
        {
            if (visited[i][j]) continue;
            visited[i][j] = true;
            rooms.push_back({});
            
            BFS(i, j, ++roomsIndex);
 
        }
    }
    
    sort(rooms.begin(), rooms.end(), cmp);
 
    cout << rooms.size() << endl;
    cout << rooms[0].nodes.size() << endl;
 
    int answer = 0;
 
    for (int i = 0; i < rooms.size(); ++i)
    {
        vector<Node>& first = rooms[i].nodes;
 
        for (int j = i + 1; j < rooms.size(); ++j)
        {
            vector<Node>& second = rooms[j].nodes;
 
            for (int l = 0; l < first.size(); ++l)
            {
                for (int m = 0; m < second.size(); ++m)
                {
                    for (int d = 0; d < 4; ++d)
                    {
                        int nextY = first[l].y + dirs[d][0];
                        int nextX = first[l].x + dirs[d][1];
 
                        if (nextY == second[m].y && nextX == second[m].x)
                        {
                            answer = max(answer, (int)first.size() + (int)second.size());
                        }
                    }
                }
            }
        }
    }
 
    cout << answer;
}

일단 처음제출했던 코드.

방의 벽정보를 bitset을 이용해서 편하게 다뤘다.

서,북,동,남 순서로 비트가 시작되기 때문에 dirs의 방향순서도 서북동남으로 했다.

 

통과는 하는데 20ms정도 나오길래 찝찝해서 다른 사람속도를 봤더니 0ms가 대부분인걸 발견.

사실 벽 한번 허물었을때의 최대방크기를 구하는 코드가 너무 무식하긴 해서 다른 풀이 참고.

내 코드같은경우는 각방을 이루는 노드들을 전부 저장해놨다가 하나씩 비교해서 바로 옆노드, 즉 벽허물었을 때 연결되면 그때의 값을 최대값으로 업데이트 했다가 출력하는 코드.

시간복잡도 계산했을 때 200만 넘게나와서 통과는 하되 20ms이상 나올만 했다.

 

그리고 풀이를 참고했을 때 내가 전혀 필요없는 계산을 했다는것을 알았다.

그냥 각 방마다 마킹하고 마지막에 [50][50]짜리 arr 한번 쓱 순회하면 끝이다. 상하좌우 검사 4번이니까 50 * 50 * 4로 끝난다.

 

struct Node
{
    int y;
    int x;
};
 
int rowSize, colSize;
bitset<4> wallInfo[50][50];
int roomsSize[2500] = { 0 };
int dirs[4][2] = { {0,-1}, {-1,0},{0,1},{1,0} };
int arr[50][50] = { 0 };
 
bool checkInRange(int y, int x)
{
    if (y < 0 || y >= rowSize || x < 0 || x >= colSize) return false;
    return true;
}
 
int BFS(int startY, int startX, int roomIndex)
{
    queue<Node> q;
    q.push({ startY,startX });
    arr[startY][startX] = roomIndex;
    
    int count = 1;
 
    while (!q.empty())
    {
        int curY = q.front().y;
        int curX = q.front().x;
        q.pop();
 
        for (int i = 0; i < 4; ++i)
        {
            int nextY = curY + dirs[i][0];
            int nextX = curX + dirs[i][1];
 
            if (!checkInRange(nextY, nextX)) continue;
            if (wallInfo[curY][curX][i] == 1) continue;
            if (arr[nextY][nextX] != 0) continue;
 
            ++count;
            arr[nextY][nextX] = roomIndex;
            q.push({ nextY,nextX });
        }
    }
 
    roomsSize[roomIndex] = count;
    return count;
}
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
 
    cin >> colSize >> rowSize;
 
    for (int i = 0; i < rowSize; ++i)
    {
        for (int j = 0; j < colSize; ++j)
        {
            int input;
            cin >> input;
 
            wallInfo[i][j] = input;
        }
    }
 
    int roomIndex = 0;
    int maxRoomSize = 0;
    for (int i = 0; i < rowSize; ++i)
    {
        for (int j = 0; j < colSize; ++j)
        {
            if (arr[i][j] != 0) continue;
            ++roomIndex;
            maxRoomSize = max(maxRoomSize, BFS(i, j, roomIndex));
        }
    }
    
    cout << roomIndex << endl;
    cout << maxRoomSize << endl;
 
    int maxDoubleRoomSize = 0;
 
    for (int i = 0; i < rowSize; ++i)
    {
        for (int j = 0; j < colSize; ++j)
        {
            for (int k = 0; k < 4; ++k)
            {
                int nextY = i + dirs[k][0];
                int nextX = j + dirs[k][1];
 
                if (!checkInRange(nextY, nextX)) continue;
                if (arr[i][j] == arr[nextY][nextX]) continue;
 
                maxDoubleRoomSize = max(maxDoubleRoomSize, roomsSize[arr[i][j]] + roomsSize[arr[nextY][nextX]]);
            }
        }
    }
 
    cout << maxDoubleRoomSize;
}