알고리즘
[SWEA] 2117. [모의 SW 역량테스트] 홈 방범 서비스
Just a devlog
2020. 4. 19. 17:32
2117. [모의 SW 역량테스트] 홈 방범 서비스
문제 링크
처음 푼 방식은 정말 무식했다.
반복문으로 마름모꼴로 범위를 점점 넓혀가면서 탐색하는 방법을 이용했다.
마름모꼴로 탐색하는 반복문을 만드는 데 시간을 너무 많이 허비했다. ( 어거지로 만들었다. )
다 풀고 나서 스터디 코드 리뷰를 통해 BFS로 푸는 방법을 보고, 다시 풀어보았다.
처음 푼 방식은 상대적으로 실행시간이 오래 걸린 대신, 메모리를 적게 썼고,
BFS를 이용했을 땐, 메모리를 많이 쓴 대신 실행 시간을 더 줄일 수 있었다.
이 문제에서 주의할 부분은
손해가 없다는 말은 이익이 0원이 되도 된다는 것.
▼ 무식하게 푼 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
|
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Solution_sw_2117_홈방범서비스 {
static int T;
static int N, M, answer; // N : 도시 갯수, M : 하나의 집 지불비용
static int[][] map;
static int service;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
T = Integer.parseInt(br.readLine());
for (int t = 1; t <= T; t++) {
String[] str = br.readLine().split(" ");
N = Integer.parseInt(str[0]);
M = Integer.parseInt(str[1]);
map = new int[N][N];
for (int i = 0; i < N; i++) {
str = br.readLine().split(" ");
for (int j = 0; j < N; j++) {
map[i][j] = Integer.parseInt(str[j]);
}
}
answer = Integer.MIN_VALUE;
for (int k = 1; k <= Math.sqrt(2) * N; k++) {
service = k * k + (k - 1) * (k - 1);
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
test(i, j, k);
}
}
}
sb.append("#" + t + " " + answer + "\n");
}
System.out.println(sb.toString());
}
static void test(int y, int x, int k) {
int house = 0;
int rate = 0;
for (int i = y - (k - 1), index = 0; i <= y; i++, index++) {
for (int j = x - index; j <= x + index; j++) {
if (isRange(i, j) && map[i][j] == 1)
house++;
}
}
for (int i = y + 1, index = k - 2; i <= y + (k - 1); i++, index--) {
for (int j = x - index; j <= x + index; j++) {
if (isRange(i, j) && map[i][j] == 1)
house++;
}
}
rate = M * house;
if (service <= rate && answer < house) {
answer = house;
}
}
private static boolean isRange(int y, int x) {
return y < N && x < N && y >= 0 && x >= 0;
}
}
|
cs |
더보기
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
|
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
public class Solution_sw_2117_홈방범서비스2 {
static int T;
static int N, M, answer; // N : 도시 갯수, M : 하나의 집 지불비용
static int[][] map;
static int[] dx = { 0, 1, 0, -1 };
static int[] dy = { -1, 0, 1, 0 };
static class Point {
int y;
int x;
public Point(int y, int x) {
this.y = y;
this.x = x;
}
@Override
public String toString() {
return "Point [y=" + y + ", x=" + x + "]";
}
}
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
T = Integer.parseInt(br.readLine());
for (int t = 1; t <= T; t++) {
String[] str = br.readLine().split(" ");
N = Integer.parseInt(str[0]); // N : 도시 갯수
M = Integer.parseInt(str[1]); // M : 하나의 집이 지불할 수 있는 비용
map = new int[N][N];
// map 입력
for (int i = 0; i < N; i++) {
str = br.readLine().split(" ");
for (int j = 0; j < N; j++) {
map[i][j] = Integer.parseInt(str[j]);
}
}
answer = 0;
// bfs 돌기
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
bfs(new Point(i, j), new boolean[N][N]);
}
}
sb.append("#" + t + " " + answer + "\n");
}
System.out.println(sb.toString());
}
private static void bfs(Point point, boolean[][] isVisited) {
int K = 0;
int house = 0;
Queue<Point> queue = new LinkedList<>();
queue.add(point);
isVisited[point.y][point.x] = true;
while (!queue.isEmpty()) {
int size = queue.size();
K++;
for (int i = 1; i <= size; i++) {
Point from = queue.poll();
if (map[from.y][from.x] == 1) {
// 집 갯수 증가
house++;
}
for (int d = 0; d < 4; d++) {
int ny = from.y + dy[d];
int nx = from.x + dx[d];
if (isRange(ny, nx) && !isVisited[ny][nx]) {
queue.add(new Point(ny, nx));
isVisited[ny][nx] = true;
}
}
}
int pay = house * M;
int service = K * K + (K - 1) * (K - 1);
if (service <= pay && answer < house) {
answer = house;
}
}
}
private static boolean isRange(int ny, int nx) {
return ny >= 0 && nx >= 0 && ny < N && nx < N;
}
}
|
cs |