알고리즘 문제풀이/백준
[백준 2234] 성곽
홍시홍
2020. 3. 19. 00:55
요구사항
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;
}