🔑SWEA_SW_1767

📁 [SW_1767] 프로세서 연결하기

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

public class Solution {
	static StringTokenizer st;
	static int[][] map;
	static ArrayList<int[]> list;
	static int N, max, totalCnt, min;
	static int[] dy = { -1, 1, 0, 0 };
	static int[] dx = { 0, 0, -1, 1 };

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

		// 테케
		int t = Integer.parseInt(br.readLine());

		for (int tc = 1; tc <= t; tc++) {
			sb.append("#").append(tc).append(" ");

			// 배열 크기
			N = Integer.parseInt(br.readLine());

			// 전체 코어 리스트
			map = new int[N][N];

			// 가장자리를 제외한 코어 리스트
			list = new ArrayList<int[]>();

			// 최대 연결 코어수
			max = 0;

			// 최소 전선 길이의 합
			min = Integer.MAX_VALUE;

			// 가장자리가 아닌 코어의 개수
			totalCnt = 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());

					// 가장 자리에 있는 것은 통과 ( 어차피 연결이 되어있기 때문에 확인할 필요 x -> 시간복잡도 감소 )
					if ((i == 0 || i == N - 1 || j == 0 || j == N - 1) && map[i][j] == 1)
						continue;

					// 가장 자리에 있는 코어가 아니면 list에 추가
					if (map[i][j] == 1) {
						list.add(new int[] { i, j });
						// 개수 추가
						totalCnt++;
					}
				}
			}

			go(0, 0);

			sb.append(min).append("\n");
		}
		System.out.println(sb);
	}

	// 부분집합을 코어 전선놓기 시도 , cCnt : 전원과 연결된 코어 수
	private static void go(int index, int cCnt) {

		// 기저조건 - 모든 코어를 시도해본 경우
		if (index == totalCnt) {
			int res = getLength();
			// 현재 연결된 코어수가 더 많다면 최대 코어수와 최소 전선 길이 합을 바꿔준다.
			if (max < cCnt) {
				max = cCnt;
				min = res;
			} else if (max == cCnt) { // 최대 연결 코어수가 같다면 더 최소인 것으로 바꾼다
				if (min > res)
					min = res;
			}
			return;
		}

		// 처리해야할 코어
		int[] core = list.get(index);
		int y = core[0];
		int x = core[1];

		// 전선 놓아보기 ( 4방향으로 )
		for (int i = 0; i < 4; i++) {
			// 놓을 수 있는지 확인 x,y 위치에서 i 방향으로 놓을 수 있으면
			if (isAvailable(y, x, i)) {
				// 현재 상태를 변경 ( 전선 놓기 ) -> 0 은 빈자리 1 은 코어 자리 2 는 전선 자리
				setStatus(y, x, i, 2);
				// 다음 core로 이동
				go(index + 1, cCnt + 1);
				// 처음에 위방향으로 두고 다 갔다왔으니 이제 다른 방향으로 두고 다 돌기 위해 다시 빈자리로 만들어준다. 전선 지우기
				// 백트래킹
				setStatus(y, x, i, 0);

			}
		}

		// 전선 놓지 않기 , 카운트 변화는 없다
		go(index + 1, cCnt);

	}

	// r, c 위치에서 d 방향으로 전선을 놓을 수 있는지 체크
	private static boolean isAvailable(int y, int x, int i) {
		int nx = x;
		int ny = y;
		
		while (true) {
			nx += dx[i];
			ny += dy[i];

			// 범위를 벗어나는 경우
			if (nx < 0 || nx >= N || ny < 0 || ny >= N)
				break;

			// 다른 코어나 전선을 만나면 return false ( 1, 2 인 경우 )
			if(map[ny][nx] >= 1) return false;
		}
		// 다른애들 안만나고 끝까지 다가서 완료
		return true;		
	}

	// r,c 위치에서 d 방향으로 전선을 놓거나(2) 지우거나(0) -> s 는 상태를 나타낼거임
	private static void setStatus(int y, int x, int i, int s) {
		int nx = x;
		int ny = y;

		// 방향 탐색
		while (true) {
			// 코어위치는 건들지 않는다. 한 방향으로 계속 간다 ( while 문 )
			nx += dx[i];
			ny += dy[i];

			// 범위를 벗어나는 경우
			if (nx < 0 || nx >= N || ny < 0 || ny >= N)
				break;

			// 안그러면 map 에 상태값으로 채운다
			map[ny][nx] = s;
		}
	}

	// 놓아진 전선의 길이의 합 계산
	private static int getLength() {
		int lCnt = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				// 전선일 경우
				if (map[i][j] == 2)
					lCnt++;
			}
		}
		return lCnt;
	}

}

🤔 나의 생각

일단 모든 문장에 주석을 달아 보았다.
먼저 문제를 보면 부분 문제들이 있다.

1. 가장자리 코어는 이미 연결되어 있는 상태
2. 전선은 직선으로 나간다.
3. 전선끼리 교차하면 안된다.
4. 최대한 많은 core에 전원을 연결하였을 경우 전선 길이의 합을 구하라 ( 여러 경우가 나올 시 합이 최소가 되는 것 )
5. 7 <= N <= 12 이고 1 <= core <= 12 이다. 이 조건을 가지고 시간복잡도를 유추할 수 있다.
   
   먼저 1번을 통해 가장자리의 core 들은 우리가 만질 필요가 없다는 것을 알게 된다.
   그래서 list에 core의 좌표를 저장할 때 가장자리 core 들은 빼주었다.
   그리고 core를 선택하는 방법을 생각해보면 core 가 5개 일 경우 5C1, 5C2, 5C3 … 5C5 이렇게 진행된다. 이 과정을 다 더하면 결국 부분집합을 구하는 구조이다. 그래서 부분집합 문제라는 것을 생각한다.
   여기서 시간복잡도를 생각하면 부분집합 구하는 문제는 보통 O(2ⁿ)이다. 그러나 여기서는 상,하,좌,우,미포함 까지 5가지 경우이기 때문에 O(5ⁿ)일 것이다. 그러나 !! 여기서 가장자리 core를 제외하고 3번 문제와 같이 나중에 전선들이 하나 둘 씩 그이고 나면 못가게 되는 경우도 많이 생길 것이다.
   그러면 대략 O(4ⁿ)이라 생각하면 n의 최대값이 12이기 때문에 4의 12승은 충분히 해낼 수 있는 시간 복잡도이다. 이 방법은 틀리지 않았다.
   그리고 필요한 것을 생각해보면 부분집합으로 코어 전선 놓기, 전선 놓을수 있는지 체크, 배열에 상태 저장, 놓아진 전선 길이의 합 메서드가 필요하다.
   그리고 여기서 core에서 4방향 ( 상,하,좌,우 )으로 탐색하는 것도 넣어준다.
   자세한 것은 주석에다 다 달아두었다.