홈 방범 서비스

https://www.swexpertacademy.com/main/solvingProblem/solvingProblem.do

저번 코드 : https://hsdevelopment.tistory.com/45

다시 풀어보았다.

처음에 시간 초과 나길래

이유가 뭔가 했더니

하나의 점에 대하여, BFS를 몇 십 번이나 반복하고 있었던 것이었다.

그리고 각 그 경우마다 처음부터 끝까지 BFS를 또 돌리고 있었다.(아래 짧은 코드 참고)

for(int k = 0; k < 2 * N; k++)
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            ans = max(ans, bfs(i, j, k));
 

그래서 생각해보니 그냥

하나의 점을 처음부터 끝까지 BFS를 돌리면서

변수 k에 대해 그 때 그 때 마다, 계산해주면 됐었다.

#include <bits/stdc++.h>
 
using namespace std;
 
int N = 0, M = 0, Map[22][22] = { 0, };
 
int dy[4] = { 0, 1, 0, -1 };
int dx[4] = { 1, 0, -1, 0 };
 
int bfs(int r, int c)
{
    int ret = 0, k = 0, home = 0;
 
    bool visit[22][22] = { false, };
    memset(visit, false, sizeof(visit));
    queue<pair<int, int> > q;
 
    q.push({ r, c });
    visit[r][c] = true;
 
    while (!q.empty() || k <= N + 10)
    {
        int qSize = q.size(), pft = 0;
 
        pft = home * M - (k*k + (k - 1)*(k - 1));
 
        if (pft >= 0) ret = max(ret, home);        
 
        while (qSize--)
        {
            int y = q.front().first;
            int x = q.front().second;
 
            q.pop();
 
            if (Map[y][x] == 1) ++home;
 
            for (int i = 0; i < 4; i++)
            {
                int ny = y + dy[i];
                int nx = x + dx[i];
 
                if (ny < 0 || ny >= N || nx < 0 || nx >= N || visit[ny][nx]) continue;
 
                visit[ny][nx] = true;
 
                q.push({ ny, nx });
            }
        }
 
        ++k;
    }
 
    return ret;
}
 
int main(void)
{
    int T = 0;
 
    scanf("%d", &T);
 
    for( int tc = 1; tc <= T; tc++ )
    {
        int ans = -1;
 
        scanf("%d %d", &N, &M);
 
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)        
                scanf("%d", &Map[i][j]);
        
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                ans = max(ans, bfs(i, j));
 
        printf("#%d %d\n", tc, ans);
    }
 
    return 0;
}