개요
브루트 포스 계열의 문제
너무 어렵게 생각하지 말고 단순하게 생각하자 !
덤으로, 마름모 모양이 BFS를 통해 구현될 수 있는 것을 명심하자
(이 부분은 다른 문제에서 두고두고 사용될 수 있는 포인트 일 것 같다)
문제 분석
N * N 크기의 지도가 주어진다.
서비스 지역의 크기에 따라 운영비용이 정해진다.
이 운영비용의 경우 다음과 같은 식에 따라 정해진다.
운영비용 = K * K + (K - 1) * (K - 1)
서비스 지역의 크기는 마름모 모양을 이루고 있고, 서비스 지역 내에 포함되어있는 집의 개수 * 서비스 비용 으로 수익을 구할 수 있다.
우리의 목표는, 회사가 손해를 보지 않으면서 최대한 많은 집에게 서비스를 제공하는 경우의 수를 찾는 것이다.
즉, 수익 - 운영비용 >= 0 으로 적어도 적자는 나지 않는 상태이면서, 마름모 모양안에 가장 많은 집이 포함되는 경우를 찾아야 한다.
여기에서 그럼 마름모 모양은 어떻게 구하느냐 라는 의문을 가지는 사람도 있을 것이다.
다양한 방법이 있을 수 있지만,나의 경우 BFS를 통해 해당 부분을 구현했다.
마름모 모양을 어떻게 BFS로 구현하지? 라는 생각이 든다면 이 이미지를 한번 보자.
빨간색 칸이 해당 depth에서 가지는 현재 노드이고, 노란색 칸은 현재 노드에서 갈 수 있는 노드들을 표시한 것이다.
K = 3 이라고 가정하면 마지막, depth가 3일때 노란색 노드는 더이상 생길 수 없다. 왜냐하면 더 이상 탐색할 수 없도록 할 것 이기 때문이다.
위의 모양을 보면, bfs 를 통한 탐색이 마름모를 만드는 것을 알 수 있다.
이러한 것을 활용하여 K의 크기에 따른 마름모 모양을 그릴 것이고 거기에 포함된 집의 개수를 세줄것이다.
마름모 모양을 그릴 수 있다면 모든 준비는 끝낫다.
모든 좌표를 마름모의 중심으로 잡아가며 K의 크기를 늘려가며 비교하면 된다.
즉,완전탐색을 하면 된다.
여기에서 고민했던 부분은 K가 몇일때까지 탐색해보아야 하는 것이다.
N의 크기가 주어지면,K가 N을 다 덮을 정도는 까지는 탐색해야한다.
즉,지도 전체가 마름모안에 들어올정도의 K까지는 탐색을 해보아야 한다는 것이다.
다만,나의 경우 여기에서 모든 집에서 얻어들일 수 있는 수익이 K에 따른 운영 비용보다 항상 작게 나오는 경우 더이상 계산하지 않도록 했다.
이는, K가 여기서 더 커지더라도 운영비용이 막대하기 때문에 아무리 모든 집을 다 포함하더라도 적자가 날것이기 때문이다.
이제 문제를 풀어보도록 하자.
문제 풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;
/**
* @author onyoo
* @performance
* @category
* @note
* @see
* https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V61LqAf8DFAWu
* @since 2023-11-08
**/
public class Solution {
static class Point{
int x,y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
static int T,N,M;
static int[][] map;
static int[] profit = new int[22]; // 도시의 최대 크기만큼 배열을 생성
static Point[] dir = {new Point(0,1),new Point(0,-1),new Point(1,0),new Point(-1,0)};
static int maxHome,home;
// 서비스를 제공받는 가장 많은 집의 개수
// 총 집의 개수 -> 이걸 통해서 해당되지 않는 범위는 자를 것
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
T = Integer.parseInt(br.readLine());
for(int i=1;i<22;i++) profit[i] = i * i + (i-1) * (i-1);
// 이익을 저장한다
// N이 가질 수 있는 최대값 + 1 그리고 1부터 시작한다고 가정하여 이익을 저장함
for(int t=1;t<T+1;t++) {
st = new StringTokenizer(br.readLine()," ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new int[N][N];
maxHome = home = 0;
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine(), " ");
for (int j = 0; j < N; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
if(map[i][j] == 1) home++;
// 집의 개수
// 전체집의 개수가 필요하다
// 모든 집의 이익을 더해도 손해가 나는지 확인하기 위함
}
}
for (int k = 1; k < 22; k++) {
// 범위
if(home * M - profit[k] < 0 ) break;
// 모든 집의 이익을 더해도 손해가 나는 상황이면 이 이상은 가지 않는다
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
bfs(i,j,k);
}
}
}
System.out.printf("#%d %d\n",t,maxHome);
}
}
static void bfs(int x,int y,int k){
// 시작지점
// 범위
Queue<Point> que = new ArrayDeque<>();
boolean[][] visited = new boolean[N][N];
int depth = 0; // 범위만큼 depth 가 깊어진다
int count = 0; // 집의 개수
que.add(new Point(x,y));
visited[x][y] = true;
while(!que.isEmpty()){
int size = que.size();
if(depth == k) break; // 해당 depth까지 오면 중단한다
for(int s = 0; s < size; s++){
Point curr = que.poll();
if(map[curr.x][curr.y] == 1) count++;
for(Point d : dir){
int nx = curr.x + d.x;
int ny = curr.y + d.y;
if(nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
if(visited[nx][ny]) continue;
visited[nx][ny] = true;
que.add(new Point(nx,ny));
}
}
depth++;
}
if(count * M - profit[k] >= 0) maxHome = Math.max(count,maxHome);
//가장 많은 집의 개수를 업데이트
//이윤이 나는 경우에만 업데이트 한다
//이윤이 큰 경우가 아니라 적자가 아닌경우에 업데이트 한다는 사실을 기억하자!
}
}