성곽

코드

#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <deque>
#include <numeric>
#include <map>
#include <stack>
#define ull unsigned long long
using namespace std;
// 0325 ~ 0515
int N,M;
int ans_cnt, ans_wide, ans_wide_remove;
int board[52][52];
bool vis[52][52];
bool vis2[2][52][52];
int record[52][52];
map<int,int> record_num;
int dx[4] = {-1, 0, 1, 0}; // 서,북,동,남
int dy[4] = {0, -1, 0, 1};
vector<pair<int,int>> room_area;
bool breakWall(int num, int n){ // n은 0,1,2,3 (1,2,4,8)
    int result = num & (1 << n);
    if(result == (1 << n)) return false;
    return true;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M; // N=가로, M=세로
    for(int i=0;i<M;i++)
        for(int j=0;j<N;j++)
            cin >> board[i][j];
    // 1,2번 수행
    for(int i=0;i<M;i++)
    {
        for(int j=0;j<N;j++)
        {
            if(vis[i][j]) continue;
            ans_cnt++; // 이 성에 있는 방의 개수
            room_area.push_back({i,j});
            int cnt = 1;
            queue<pair<int,int>> q;
            q.push({i,j});
            vis[i][j] = true;
            record[i][j] = ans_cnt;
            while(!q.empty())
            {
                auto cur = q.front(); q.pop();
                for(int dir=0;dir<4;dir++)
                {
                    int ny = cur.first + dy[dir];
                    int nx = cur.second + dx[dir];
                    int num = board[cur.first][cur.second];
                    if(nx<0 or ny<0 or nx>=N or ny>=M) continue;
                    if(vis[ny][nx] or !breakWall(num,dir)) continue;
                    q.push({ny,nx});
                    vis[ny][nx] = true;
                    record[ny][nx] = ans_cnt;
                    cnt++;
                }
            }
            record_num[ans_cnt] = cnt;
            ans_wide = max(ans_wide, cnt);
        }
    }
    // 3번 수행
    for(int i=0;i<room_area.size();i++)
    {
        /* vis2 초기화 */
        for(int z=0;z<1;z++)
            for(int j=0;j<M;j++)
                fill(vis2[z][j], vis2[z][j]+N, false);
        /* BFS 수행 */
        auto cur_pos = room_area[i];
        int cur_room_num = record[cur_pos.first][cur_pos.second];
        queue<pair<pair<int,int>,int>> dq; // {{y,x},status}
        dq.push({cur_pos,0});
        vis2[0][cur_pos.first][cur_pos.second] = true;
        int sum = record_num[cur_room_num];
        while(!dq.empty())
        {
            auto cur = dq.front(); dq.pop();
            for(int dir=0;dir<4;dir++)
            {
                int ny = cur.first.first + dy[dir];
                int nx = cur.first.second + dx[dir];
                int num = board[cur.first.first][cur.first.second];
                int status = cur.second;
                if(nx<0 or ny<0 or nx>=N or ny>=M) continue;
                if(!breakWall(num, dir)){
                    if(status == 1) continue;
                    status++;
                }
                if(vis2[status][ny][nx]) continue; 
                vis2[status][ny][nx] = true;
                // dq.push({{ny,nx},status});  여기에 있으면 57%에서 실패처리
                if(cur_room_num != record[ny][nx]){
                    sum = max(sum, record_num[cur_room_num] + record_num[record[ny][nx]]);
                    continue;
                }
                dq.push({{ny,nx},status});  // 새로운 방 왔을 때 바로 종료하고 큐에 안넣으면 성공처리
            }
        }
        ans_wide_remove = max(ans_wide_remove, sum);
    }
    cout << ans_cnt << '\n' << ans_wide << '\n' << ans_wide_remove << '\n';
    return 0;
}

• 핵심
  • 비트마스킹을 이용해서 벽이 없다면 갈 수 있도록 설정 --> 1,2번 BFS
  • 벽이 있어도 status가 0이면 (벽을 부수지 않았으면) status++하고 진행 --> 3번 BFS
  • 영역간 방 개수의 합을 구하기 위해 각 영역별로 숫자를 부여하고 영역별 룸 개수를 기록
    (record[][] --> 배열 / record_num --> map)

• 아이러니한 점
  • 3번 BFS를 수행할 때 벽을 부순 뒤 새로운 방에 갔을 때
    • queue에 해당 점을 넣으면 ---> 오답
    • queue에 해당 점을 넣지 않으면 --> 정답
  • 사실 새로운 방에 오면 갱신하고 queue에 넣지 않는게 맞긴한데, 넣어도 문제가 없을것같은데 오답처리가 됨

• 느낀 점
  • BFS 수행시 목표 달성을 한 뒤 queue에 최대한 넣지 않게 꼼꼼하게 코딩하자