백준[C++] 2234 성곽

<조건 분석>

1. 방이 최대 50 X 50. DFS의 시간 복잡도는 O(정점 + 간선)임

2. 이중 for문으로 순회한다 해도 visited배열로 딱 한번 씩 방문하기 때문에, M*N 즉 2500번 정도임

3. 엄청 널널함.

 

 

<문제 해결 포인트>

1. Connected Component 문제라는 것을 단번에 알아차려야 함. (방이 여러개, 방 갯수를 구하면서 방의 크기도 구함)

2. room별로 방의 크기를 저장하고, 각 방마다의 cnt를 room의 id로 활용해야 함.

3. visited 배열에 각 방마다의 cnt로 방문 표시를 찍어야 함.

4. 이렇게 구분해놓으면 벽을 부수는 것은 일일히 순회하며 부숴보면 됨.

 

 

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

int N, M;

int board[51][51];
int visited[51][51];

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

int roomcnt = 0;
std::vector<int> room;
int res = 0;

int DFS(int y, int x, int cnt)
{
    visited[y][x] = cnt;
    int ret = 1;

    for (int i = 0; i < 4; i++)
    {
        if (board[y][x] & (1 << i)) continue;

        int ny = y + dy[i];
        int nx = x + dx[i];

        if (ny < 0 || nx < 0 || ny >= M || nx >= N) continue;
        if (visited[ny][nx]) continue;

        ret += DFS(ny, nx, cnt);
    }

    return ret;
}


int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> N >> M;
    room.resize(50);
    int roomsize = 0;

    for (int i = 0; i < M; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> board[i][j];
        }
    }

    for (int i = 0; i < M; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (visited[i][j]) continue;
            room[roomcnt] = DFS(i, j, roomcnt);
            roomsize = max(roomsize, room[roomcnt]);
            roomcnt++;
        }
    }

    for (int i = 0; i < M; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (j + 1 < N)
            {
                int a = visited[i][j];
                int b = visited[i][j + 1];
    
                if (a != b)
                {
                    res = ::max(res, room[a] + room[b]);
                }
            }
            if (i + 1 < M)
            {
                int c = visited[i][j];
                int d = visited[i + 1][j];
    
                if (c != d)
                {
                    res = ::max(res, room[c] + room[d]);
                }
            }
        }
    }


    cout << roomcnt <<"\n";
    cout << roomsize<<"\n";
    cout << res << "\n";

    return 0;
}