[알고리즘] 프로세서 연결하기
2024. 2. 29. 15:10ㆍ알고리즘 풀이/Java
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4suNtaXFEDFAUf#none
import java.awt.Point;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class Solution {
static int N;
static int maxCount;
static int minSum;
static int accSum;
static int[][] map;
static int[] dr = {-1, 1, 0, 0};
static int[] dc = {0, 0, -1, 1};
static List<Point> cores;
static int C;
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int T = Integer.parseInt(br.readLine());
for (int testCase = 1; testCase <= T; testCase++) {
N = Integer.parseInt(br.readLine());
map = new int[N][N];
cores = new ArrayList<>();
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 && 1<= i && i <= N-2 && 1<= j && j <= N-2) {
cores.add(new Point(i, j));
}
}
}
maxCount = Integer.MIN_VALUE;
minSum = Integer.MAX_VALUE;
accSum = 0;
C = cores.size();
exhaustiveSearch(0, 0);
sb.append("#").append(testCase).append(" ").append(minSum).append("\n");
}
System.out.println(sb);
}
private static void exhaustiveSearch(int depth, int count) {
if (depth == C) {
if (count > maxCount) {
minSum = accSum;
maxCount = count;
} else if (count == maxCount) {
minSum = Math.min(minSum, accSum);
}
return;
}
if (count + (C - depth) < maxCount) {
return;
}
for (int i = 0; i < 5; i++) {
int dir = i;
int r = cores.get(depth).x;
int c = cores.get(depth).y;
if (i == 4) {
exhaustiveSearch(depth + 1, count);
} else if (validLine(r, c, dir)) {
makeLine(r, c, dir);
exhaustiveSearch(depth + 1, count + 1);
removeLine(r, c, dir);
}
}
}
private static int findSum() {
int count = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (map[i][j] == 2) {
count++;
}
}
}
return count;
}
private static void removeLine(int r, int c, int dir) {
int nr = r;
int nc = c;
while (true) {
nr += dr[dir];
nc += dc[dir];
if (!(0 <= nr && nr < N && 0 <= nc && nc < N)) {
return;
}
map[nr][nc] = 0;
accSum--;
}
}
private static boolean validLine(int r, int c, int dir) {
int nr = r;
int nc = c;
while (true) {
nr += dr[dir];
nc += dc[dir];
if (!(0 <= nr && nr < N && 0 <= nc && nc < N)) {
return true;
}
if (map[nr][nc] == 1 || map[nr][nc] == 2) {
return false;
}
}
}
private static void makeLine(int r, int c, int dir) {
int nr = r;
int nc = c;
while (true) {
nr += dr[dir];
nc += dc[dir];
if (!(0 <= nr && nr < N && 0 <= nc && nc < N)) {
return;
}
accSum++;
map[nr][nc] = 2;
}
}
}
나의 풀이
- static 초기화를 잘해주자
- 최댓값을 갱신해줄 때 새로운 최댓값이 이전 최댓값 변수를 덮어써야 한다. 조심하자!!!!!
- 현재 선택된 프로세서의 개수 + 고려되지 않은 프로세서의 개수 < 지금까지 최대로 선택된 프로세서의 개수이면 가지치기를 진행한다. 즉, 그 다음 깊이로 넘어가지 않고 다른 가지를 탐색한다.
'알고리즘 풀이 > Java' 카테고리의 다른 글
[알고리즘] LinkedList (0) | 2024.03.10 |
---|---|
[알고리즘] ArrayList 메서드별 시간 복잡도 (0) | 2024.03.09 |
[알고리즘] 디버깅 꿀팁 (0) | 2024.02.29 |
[알고리즘] 말이 되고픈 원숭이 (3) | 2024.02.28 |
[알고리즘] 파이프 옮기기 1 (1) | 2024.02.28 |