[백준 2234] 성곽

요구사항

1. bfs를 이용하여 성곽의 최대 크기와 성의 갯수 구하기

2. 성곽을 1개 허물었을때 최대 크기 구하기

 

풀이

동서남북이 열려져 있는가 확인 하기 위해서

map[i][j] & (1<<k) 를 하면 해당 방향으로 열려져 있다면 (1<<k) 값을 가질꺼고 아니면 0이 될 것이다

또한 안열려져있는 부분 열기 위해서는

map[i][j] | (1<<k) 하면 k번째 0인 비트가 1로 set 된다

map[i][j] & ~(1<<k)를 하면 k번재 비트 0으로 set 된다

 

 

https://jaimemin.tistory.com/957

해당 글을 참조하여 비트 부분만 바꾸었다

#include <iostream>
#include <string.h>
#include <queue>

#include <algorithm>

using namespace std;



const int MAX = 50;



typedef struct

{

    int y, x;

}Dir;



Dir moveDir[4] = { {0, -1}, {-1, 0}, {0, 1}, {1, 0} };



int N, M;

int area;

int graph[MAX][MAX];

bool visited[MAX][MAX];



int BFS(int y, int x)

{

    queue<pair<int, int>> q;

    q.push({ y, x });

    visited[y][x] = true;

    int cnt = 1;



    while (!q.empty())

    {

        int curY = q.front().first;

        int curX = q.front().second;

        q.pop();



        int bit = 1;

        //서,북,동,남 벽 확인

        for (int i = 0; i < 4; i++)

        {

            if (!(graph[curY][curX] & (1<<i)))

            {

                int nextY = curY + moveDir[i].y;

                int nextX = curX + moveDir[i].x;

                //부시면 안되는 벽 부셨을 경우

                if (!(0 <= nextY && nextY < M && 0 <= nextX && nextX < N))

                    continue;



                //방문하지 않은 곳

                if (!visited[nextY][nextX]) {

                    cnt++;

                    visited[nextY][nextX] = true;

                    q.push({ nextY, nextX });

                }

            }

            bit <<= 1;

        }

    }

    return cnt;

}



int main(void)

{

    ios_base::sync_with_stdio(0);

    cin.tie(0);

    cin >> N >> M;



    for (int i = 0; i < M; i++)

        for (int j = 0; j < N; j++)

            cin >> graph[i][j];



    int cnt = 0;

    for (int i = 0; i < M; i++)

        for (int j = 0; j < N; j++)

            if (!visited[i][j])

            {

                area = max(area, BFS(i, j));

                cnt++;

            }



    cout << cnt << "\n";

    cout << area << "\n";

    //벽을 없애보자

    for (int i = 0; i < M; i++)

        for (int j = 0; j < N; j++)

            for (int k = 0; k <4; k++)

                if (graph[i][j] & (1<<k))

                {

                    memset(visited, false, sizeof(visited));

                    
                    graph[i][j] = graph[i][j] & ~(1 << k);
                    area = max(area, BFS(i, j));
                    graph[i][j] = graph[i][j] | (1 << k);
                    

                }



    cout << area << "\n";

    return 0;

}