[소프트웨어 익스퍼트 아카데미][SWEA][모의 SW 역량테스트][ C++][2117번] 홈 방범 서비스

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V61LqAf8DFAWu

SW Expert Academy

 

코드

#include<iostream>
#include<algorithm>
#include<queue>
#include<memory.h>
using namespace std;
struct q_info {
    int x;
    int y;
};
int N, M;
int map[21][21];
int ans;
queue<q_info> q;
queue<q_info> q_temp;
int p_x[4] = { 1,0,-1,0 };
int p_y[4] = { 0,1,0,-1 };
bool visited[21][21];
 
void bfs() {
    for (int YY = 1; YY <= N; YY++) {
        for (int XX = 1; XX <= N; XX++) {
            int h_cnt = 0;
            memset(visited, false, sizeof(visited));
            int K_cnt = 1;
            q_info cur;
            cur.x = XX;
            cur.y = YY;
            q_temp.push(cur);
            visited[cur.y][cur.x] = true;
            if (map[YY][XX] == 1)
                h_cnt++;
            while (!q_temp.empty()) {
                int q_end = q_temp.size();
                K_cnt++;
                for (int i = 0; i < q_end; i++) {
                    q_info next_q = q_temp.front();
                    q_temp.pop();
                    for (int dis = 0; dis < 4; dis++) {
                        int nx = next_q.x + p_x[dis];
                        int ny = next_q.y + p_y[dis];
                        if (nx > 0 && nx < N + 1 && ny>0 && ny < N + 1 && !visited[ny][nx]) {
                            visited[ny][nx] = true;
                            if (map[ny][nx] == 1)
                                h_cnt++;
                            q_info aaa;
                            aaa.x = nx;
                            aaa.y = ny;
                            q_temp.push(aaa);
                        }
                    }
                }
                if ((h_cnt*M - (K_cnt*K_cnt + (K_cnt - 1)*(K_cnt - 1))) >= 0)
                    ans = max(ans, h_cnt);
 
            }//whlie
        }
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int T;
    scanf("%d", &T);
    for (int t = 1; t <= T; t++) {
        scanf("%d %d", &N, &M);
        for (int Y = 1; Y <= N; Y++) {
            for (int X = 1; X <= N; X++) {
                scanf("%d", &map[Y][X]);
            }
        }
        ans = 1;
        bfs();
        printf("#%d %d\n", t, ans);
    }
}

해설

bfs를 사용해서 풀었습니다.