백준 2234 성곽

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

2234번: 성곽

 

#define NSIZE 50*3
#define MSIZE 50*2
#include<stdio.h>
#include<iostream>
#include<string.h>
using namespace std;
int input[NSIZE][MSIZE];
int chk[NSIZE][MSIZE];
int max1 = 0x80000000;
int N, M;
void init() {
    cin >> M >> N;
    for (int i = 0; i < N; i++){
        for (int j = 0; j < M; j++) {
            cin >> input[i][j];
            }        
        }            
}
int cnt;
int dy[] = { 0,-1,0,1 };
int dx[] = { -1,0,1,0 };
/*
00 01 
10 11
서,왼쪽 0 
북,위쪽 1
동,오른 2
남,아래 3
*/
int ret = 0;
void dfs(int y, int x,int cnt) {
    if (max1 < ret)max1 = ret;
    int a = 0;
    for (int dir = 0; dir < 4; dir++) {
        int ny = y + dy[dir];
        int nx = x + dx[dir];
        if (!(ny < 0 || ny >= N || nx < 0 || nx >= M)) {
            if (!(input[y][x] & 1 << a)&&chk[ny][nx]==0) {
                ret++;
                chk[ny][nx] = cnt;
                dfs(ny, nx, cnt);
            }
        }
        a++;
    }
}
void search() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (chk[i][j] == 0) {
                cnt++;
                ret = 1;
                chk[i][j] = cnt;
                dfs(i, j,cnt);
            }
        }
    }
    cout << cnt << endl << max1 << endl;
    max1 = 0x80000000;
    for (int y = 0; y < N; y++) {
        for (int x = 0; x < M; x++) {
            int copyNum = input[y][x];
            for (int k = 0; k < 4; k++) {
                if (input[y][x] & 1 << k) {
                    input[y][x] = input[y][x] ^ 1 << k;
                    memset(chk, 0, sizeof(chk));
                    cnt = 0;
                    for (int i = 0; i < N; i++) {
                        for (int j = 0; j < M; j++) {
                            if (chk[i][j] == 0) {
                                cnt++;
                                ret = 1;
                                chk[i][j] = cnt;
                                dfs(i, j, cnt);
                            }
                        }
                    }
                }                
                    input[y][x] = copyNum;
            }
            input[y][x] = copyNum;
        }
    }
    cout<< max1 << endl;
}
int main(void) {
    
    init();
    search();
    
    return 0;
}

이문제는 무조건은 아니지만 비트마스크로 해야지 정말 쉽습니다.

사실 비트마스크를 문제를 풀었던것이 고작 한문제 정도여서 처음에는 감도 안잡히는 문제였는데 

샤워하다가 갑자기 아 그냥 이렇게 해도 되나? 했는데 되더라구요. ㅋㅋㅋ 

제가 천재라서 그런게 아닙니다. 원래 알고리즘이란게 안되도 샤워할때나 김밥 먹을때 아이디어가 생각나는거라고

백준 선생님이 세미나때 가르쳐 주시더라구요. 강남 멤버쉽에 있을때 ㅋㅋ 여러분도 포기하지 마세요. 한번 알면 

적용하는것은 어렵지 않습니다.

본론으로 들어가봅시다.

 

말이 쉬울수  있는데 연산만 잘해서 잘돌려주면됩니다. 특히 저런 형식은 변하지 않으니 

일단 항상 모르면 외우고 적용해보면서 이해 하시면됩니다. 저도 이렇게 할수 있는데 여러분들은 

더잘할 수 있습니다.

오늘은 뭔가 하나의 지식을 뇌에 새기는 날이였네요. 여러분들도 파이팅