SWEA 2117 홈 방문 서비스(BFS)

SW Expert Academy

최대한 많은 집에 홈 방범 서비스를 제공

손해를 보지 않으면서 홈 방범 서비스를 가장 많은 집들에 제공하는 서비스 영역
==> 보안회사의 이익이 그냥 양수만 되면 된다는 소리임. 똑같은 서비스 집 수에서 비교할 필요x,

그냥 단순히 서비스 양만 많으면 됨

if k로 되는 운영비용 > 서비스 제공받는 집을 통해 얻는 수익
  break; //현재 k보다 큰 k들은 어짜피 음수나오니까 더 보지 않겠다는 거임

 

마름모 방문처리 해야되니까 1. 맨해튼거리 k인 애들, 2. bfs

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Solution_2117 {
    static int N,M,res,house_cnt;
    static int[][] board;
    static int[] dx = {1,-1,0,0};
    static int[] dy = {0,0,1,-1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int T = Integer.parseInt(st.nextToken());
        for (int tc = 1; tc < T+1; tc++) {
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());

            board = new int[N][N];

            house_cnt = 0;
            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < N; j++) {
                    board[i][j] = Integer.parseInt(st.nextToken());
                    if (board[i][j] == 1)
                        house_cnt++;
                }
            }

        res = 0;
        int K = 1;

        while (true){
            if ((house_cnt * M) - (K * K + (K - 1) * (K - 1)) < 0)
                break;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    res = Math.max(res,bfs(i,j,K));
                }
            }
            K++;
        }
            System.out.println("#"+tc+" "+res);

        }

    }

    public static int bfs(int r, int c,int k){
        int house = 0;

        boolean[][] visited = new boolean[N][N];
        Queue<int[]> queue = new ArrayDeque<>();
        queue.add(new int[]{r,c,0});
        visited[r][c] = true;

        if (board[r][c] == 1)
            house++;

        while(!queue.isEmpty()){
            int[] poll_data = queue.poll();
            int x = poll_data[0];
            int y = poll_data[1];
            int length = poll_data[2];
            if (length == k-1){
                if ((house*M) - (k * k + (k - 1) * (k - 1)) < 0)
                    return 0;
                else
                    return house;
            }
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (nx<0 || ny<0 || nx>=N || ny>=N)
                    continue;
                if (!visited[nx][ny]){
                    if (board[nx][ny] == 1)
                        house++;
                    visited[nx][ny] = true;
                    queue.add(new int[]{nx,ny,length+1});
                }
            }
        }
        return 0;
    }





}