[SW1767] 프로세서 연결하기

🚩 문제 설명

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4suNtaXFEDFAUf&categoryId=AV4suNtaXFEDFAUf&categoryType=CODE&problemTitle=%ED%94%84%EB%A1%9C%EC%84%B8%EC%84%9C&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1&&&&&&&&& 

SW Expert Academy

◾ 가능한 프로세서 코어를 많이 연결할 때, 프로세서 전선의 최소의 합을 구하는 문제

 

 

 

 

---

 

 

 

✅ 입출력

변수 설명
T: test case
N: map 크기
return ➡️ 코어를 최대한 많이 연결할 때, 프로세서 전선의 최소합

✔️ 예제 1

1
7    
0 0 1 0 0 0 0
0 0 1 0 0 0 0
0 0 0 0 0 1 0
0 0 0 0 0 0 0
1 1 0 1 0 0 0
0 1 0 0 0 0 0
0 0 0 0 0 0 0

#1 12

 

 

 

---

 

 

 

📑 문제 풀이

with 자바 (Java)

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;


public class Solution {
	private static int ans, T, N, size, coreMax, lineCnt;
	private static int[][] map;

	private static ArrayList<Core> list = new ArrayList<>();

	// 좌우상하
	private static int[] dx = { -1, 1, 0, 0 };
	private static int[] dy = { 0, 0, -1, 1 };


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

		T = Integer.parseInt(br.readLine());

		for (int t = 1; t <= T; t++) {
			N = Integer.parseInt(br.readLine());
			map = new int[N][N];

			// 초기화
			coreMax = 0;
			ans = Integer.MAX_VALUE;
			list.clear();

			for (int i = 0; i < N; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				for (int j = 0; j < N; j++) {
					int m = map[i][j] = Integer.parseInt(st.nextToken());
					if (m == 1) {
						if ((i == 0 || i == N - 1 || j == 0 || j == N - 1)) continue;
						list.add(new Core(i, j));
					}

				}

			}

			size = list.size();

			// 탐색
			subset(0, 0, 0);

			// 출력
			System.out.println("#" + t + " " + ans);

			// break;
		} // end tc

	} // end main


	// depth
	// coreCnt: 코어의 개수
	// sum: 현재까지의 전선 라인 길이의 총합
	private static void subset(int dep, int coreCnt, int sum) {
		if (dep == size) {
			if (coreMax < coreCnt) {
				coreMax = coreCnt;
				ans = sum;
			} else if (coreMax == coreCnt) {
				if (ans > sum) ans = sum;
			}

			return;
		}

		for (int d = 0; d < 4; d++) {
			Core core = list.get(dep);
			int y = core.y;
			int x = core.x;

			// 현재 코어 위치에서 해당 방향으로 연결이 가능한지 확인
			if (check(y, x, d)) {
				setLine(y, x, d, 2); // 전선 놓기
				subset(dep + 1, coreCnt + 1, sum + lineCnt);
				setLine(y, x, d, 0); // 놓은 전선 제거하기
			}

		}

		subset(dep + 1, coreCnt, sum); // 코어 선택 안함
	} // end dfs


	private static void setLine(int y, int x, int d, int op) {
		int ny = y + dy[d];
		int nx = x + dx[d];

		lineCnt = 0;
		while (true) {
			if (ny < 0 || ny >= N || nx < 0 || nx >= N) break;
			map[ny][nx] = op;
			lineCnt++;

			ny += dy[d];
			nx += dx[d];
		}

	} // end setLine


	private static boolean check(int y, int x, int d) {
		int ny = y + dy[d];
		int nx = x + dx[d];

		while (true) {
			if (ny < 0 || ny >= N || nx < 0 || nx >= N) break;
			if (map[ny][nx] != 0) return false;

			ny += dy[d];
			nx += dx[d];
		}

		return true;
	} // end check


	static class Core {
		int y, x;


		public Core(int y, int x) {
			super();
			this.y = y;
			this.x = x;
		}


		@Override
		public String toString() {
			return "Core [y=" + y + ", x=" + x + "]";
		}

	} // end Core
}

💬 Point

➡️  부분집합을 이용하여 집합에 포함된 코어 카운트와 전선의 길이 합을 구한다.

 

// depth
// coreCnt: 코어의 개수
// sum: 현재까지의 전선 라인 길이의 총합
private static void subset(int dep, int coreCnt, int sum) {
    if (dep == size) {
        if (coreMax < coreCnt) {
            coreMax = coreCnt;
            ans = sum;
        } else if (coreMax == coreCnt) {
            if (ans > sum) ans = sum;
        }

        return;
    }

    for (int d = 0; d < 4; d++) {
        Core core = list.get(dep);
        int y = core.y;
        int x = core.x;

        // 현재 코어 위치에서 해당 방향으로 연결이 가능한지 확인
        if (check(y, x, d)) {
            setLine(y, x, d, 2); // 전선 놓기
            subset(dep + 1, coreCnt + 1, sum + lineCnt);
            setLine(y, x, d, 0); // 놓은 전선 제거하기
        }

    }

    subset(dep + 1, coreCnt, sum); // 코어 선택 안함
} // end dfs

◾ 코어가 만약 K개 라고 할때, 0 ~ K 개 까지의 코어를 연결할 수 있다.

◾ 연결된 코어의 개수와 전선 길이의 합을 매개변수로 넣어 부분 집합 재귀를 돈다.

◾ 만약 depth 가 K 개와 같다면, 모든 코어가 연결되는지 안되는지 확인을 해 본 것이므로 return 을 한다.

◾ 여기서 값을 갱신해야한다.

◾ 코어가 최대로 연결되었을 때, 연결되어 있는 전선의 최소의 합을 구해야한다.

 

for (int d = 0; d < 4; d++) {
    Core core = list.get(dep);
    int y = core.y;
    int x = core.x;

    // 현재 코어 위치에서 해당 방향으로 연결이 가능한지 확인
    if (check(y, x, d)) {
        setLine(y, x, d, 2); // 전선 놓기
        subset(dep + 1, coreCnt + 1, sum + lineCnt);
        setLine(y, x, d, 0); // 놓은 전선 제거하기
    }

}

◾ 방향을 따지면서 현재 코어에서 (depth) 해당 방향으로 전선이 연결이 가능한지 확인을 해본다.

◾ 만약 연결이 가능하다면 -> 전선을 놓는다.

◾ 전선을 놓고, 코어를 카운팅 한다.

◾ 놓은 전선을 다시 제거를 해서 다른 방향을 따져본다.

◾ 이렇게 되면, 모든 코어 카운팅에 대해서 상하좌우 4방향을 따질 수 있게 된다. 

 

private static void setLine(int y, int x, int d, int op) {
    int ny = y + dy[d];
    int nx = x + dx[d];

    lineCnt = 0;
    while (true) {
        if (ny < 0 || ny >= N || nx < 0 || nx >= N) break;
        map[ny][nx] = op;
        lineCnt++;

        ny += dy[d];
        nx += dx[d];
    }

} // end setLine

◾ 전선을 해당 방향으로 쭉 놓는다.

◾ 전선을 놓을 때, 전선의 길이가 결정되므로 길이를 카운팅 한다.

◾ 부분집합의 매개변수로 해당 값이 전선의 총합에 계속 더해진다.

 

private static boolean check(int y, int x, int d) {
    int ny = y + dy[d];
    int nx = x + dx[d];

    while (true) {
        if (ny < 0 || ny >= N || nx < 0 || nx >= N) break;
        if (map[ny][nx] != 0) return false;

        ny += dy[d];
        nx += dx[d];
    }

    return true;
} // end check

◾ 연결이 가능한지 아닌지 확인하는 함수이다.

◾ 만약, 해당 위치가 0이 아니라면 전선을 놓을 수 없는 것이다. 그렇다면 return false 한다.

◾ 전선을 놓을 수 있다면 쭉 전선을 놓는다.

 

 

 

 

 

 

 

 

 

 

# SW 프로세서 연결하기 java

 

---