SWEA 2117번
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V61LqAf8DFAWu
문제
생각하기
-
BFS문제이다.
- 왜냐? 마름모 모양으로 퍼져나가므로 집을 기준으로 BFS를 거리만큼만 탐색해주면 된다.
-
근데 4중 for문을 통해서 BFS 안쓰고도 풀 수 있음
-
집을 기준으로 탐색하는게 아니고 전체 배열을 탐색해야 하므로, 부르트포스임
동작
일반적인 BFS탐색은 특별히 설명할 부분이 없어서 4중 for문을 기준으로 설명
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
for (int k = 1; k <=N + 1; k++) {
int operatingExpenses = operatingExpensesCalc(k);
int saveHomeCount = 0;
for (Coordinates cor : houseList) {
int targetX = cor.x;
int targetY = cor.y;
int distDiff = distCalc(i, j, targetX, targetY);
if (distDiff < k) {
saveHomeCount++;
}
}
if (0 <= ProfitAndLossCalc(operatingExpenses, saveHomeCount)) {
// 안전구역에 들어가는 집이 하나라도 있으면 손익계산 해서 최댓값 갱신해서 결과 찾기
result = Math.max(result, saveHomeCount);
}
}
}
}
가장 바깥에 있는 2중 for문 2개는 이 문제 특성상 발생하는 운영비용에서 이익을 계산하기 위해서는 집을 기준으로 배열을 탐색하는 것이 아닌, 집이 아닌 곳 까지 포함하여 전체 배열을 탐색해야 한다.
그러므로 하나의 기준점을 만드는 for문이다.
3번째 for문은 k의 값을 1씩 증가한다. k는 거리값인데, 기준점을 시작으로 k의 범위에 들어있냐 없냐를 결정할 수 있는 범위를 계속 늘려주는 for문이된다.
다음 4번째 for문은 집의 좌표만 담긴 값을 가져와서 집을 기준으로 for문을 돈다.k값을 거리값으로 설정했으니 이제 기준점으로 부터 모든 집과의 거리를 계산하여 해당 집이 k거리 안에 들어오는 여부를 파악하면 우리는 결국 이익을 계산할 수 있게된다.
BFS
4중 for문
코드
Java
4중 for문
import java.util.*;
import java.io.*;
public class Solution {
static int N, M, result, maxProfit;
static int[][] map;
static List<Coordinates> houseList;
private static class Coordinates {
int x;
int y;
public Coordinates(int x, int y) {
this.x = x;
this.y = y;
}
} // End of Coordinates class
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder();
StringTokenizer st;
int T = Integer.parseInt(br.readLine());
for (int t = 1; t <= T; t++) {
sb.append('#').append(t).append(' ');
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
init();
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) {
houseList.add(new Coordinates(i, j));
}
}
}
solution();
sb.append(result).append('\n');
}
bw.write(sb.toString());
bw.close();
} // End of main
private static void solution() {
// 바깥 2중 for문은 기준점을 만드는 전체 배열 탐색 for문
// 각 집간의 거리를 계산해서 포함되는 집만 찾기
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
for (int k = 1; k <=N + 1; k++) {
int operatingExpenses = operatingExpensesCalc(k);
int saveHomeCount = 0;
for (Coordinates cor : houseList) {
int targetX = cor.x;
int targetY = cor.y;
int distDiff = distCalc(i, j, targetX, targetY);
if (distDiff < k) {
saveHomeCount++;
}
}
if (0 <= ProfitAndLossCalc(operatingExpenses, saveHomeCount)) {
// 안전구역에 들어가는 집이 하나라도 있으면 손익계산 해서 최댓값 갱신해서 결과 찾기
result = Math.max(result, saveHomeCount);
}
}
}
}
} // End of solution
private static int ProfitAndLossCalc(int operatingExpenses, int saveHomeCount) {
return (saveHomeCount * M) - operatingExpenses;
} // End of ProfitAndLossCalc
private static int distCalc(int x1, int y1, int x2, int y2) {
return Math.abs(x1 - x2) + Math.abs(y1 - y2);
} // End of distCalc
private static int operatingExpensesCalc(int k) {
return k * k + (k - 1) * (k - 1);
} // End of operatingExpensesCalc
private static void init() {
map = new int[N][N];
result = 0;
houseList = new ArrayList<>();
maxProfit = -1;
} // End of init
} // End of Main class
BFS
import java.util.*;
import java.io.*;
public class Solution {
static int N, M, maxBenefit, result;
static int[][] arr;
static int[] dirX = {0, 0, -1, 1};
static int[] dirY = {-1, 1, 0, 0};
static class Coordinates {
int x;
int y;
int dist;
public Coordinates(int x, int y, int dist) {
this.x = x;
this.y = y;
this.dist = dist;
}
} // End of Coordinates class
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder();
StringTokenizer st;
int T = Integer.parseInt(br.readLine());
for (int t = 1; t <= T; t++) {
sb.append('#').append(t).append(' ');
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken()); // 집 하나당 지불하는 비용.
init();
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
for (int k = 1; k <= N+1; k++) { // 방범 면적의 크기 증가.
int protectArea = preventionAreaCalc(k); // 방범 면적 계산
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
BFS(i, j, k, protectArea);
}
}
}
sb.append(result).append('\n');
}
bw.write(sb.toString());
bw.close();
} // End of main
// 어차피 K값은 BFS탐색 전에 고정됨. K는 한번만 계산하면 그 값을 활용할 수 있음
private static void BFS(int x, int y, int distLimit, int protectArea) {
boolean[][] isVisited = new boolean[N][N];
isVisited[x][y] = true;
int homeCount = 0;
if (arr[x][y] == 1) {
homeCount++;
}
Queue<Coordinates> que = new LinkedList<>();
que.offer(new Coordinates(x, y, 1));
while (!que.isEmpty()) {
Coordinates cor = que.poll();
for (int i = 0; i < 4; i++) {
int nowX = cor.x + dirX[i];
int nowY = cor.y + dirY[i];
int dist = cor.dist;
if (rangeCheck(nowX, nowY) && !isVisited[nowX][nowY] && dist < distLimit) {
isVisited[nowX][nowY] = true;
que.offer(new Coordinates(nowX, nowY, dist + 1));
if (arr[nowX][nowY] == 1) {
homeCount++;
}
}
}
}
if (benefitCalc(protectArea, homeCount) >= 0 && maxBenefit <= benefitCalc(protectArea, homeCount)) {
result = Math.max(result, homeCount);
}
} // End of BFS
private static int benefitCalc(int area, int homeCount) { // 이익을 계산하는 메소드
// 방범 면적 - 집의 개수 * M
return (homeCount * M) - area;
} // End of calc
private static int preventionAreaCalc(int K) {
return K * K + (K - 1) * (K - 1);
} // End of preventionAreaCalc
private static boolean rangeCheck(int nowX, int nowY) {
return nowX >= 0 && nowX < N && nowY >= 0 && nowY < N;
} // End of rangeCheck
private static void init() {
result = Integer.MIN_VALUE;
maxBenefit = Integer.MIN_VALUE;
arr = new int[N][N];
} // End of init
} // End of Main class
