[삼성 SW Expert Academy] 1767. 프로세서 연결하기 [JAVA]

Problem

※ SW Expert Academy는 문제의 무단 복제를 금지하고 있기 때문에, 기재하지 못한 점 양해 부탁드립니다.

Link

※ 하단의 Link를 클릭해도, 로그인 후 열람이 가능합니다.

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4suNtaXFEDFAUf

SW Expert Academy

Solution

 Q1. bfs vs dfs vs 완탐 vs 최적해 바로구하기 ...??
 A1. dfs + 완탐 
 R1. 문제에서 묻는
 조건 1) 최대한 많은 Core에 전원을 연결하였을 경우, 전선의 길이의 합을 구하자. 
 조건 2) 여러 방법이 있을 경우, 전선의 길이의 합이 최소가 되는 값을 구하라.
    = 각 core에 4방으로 전선을 연결할 수 있는지 확인 후, 모든 core에 대해서 연결해봄으로써 최적해를 도출 해야한다.
    = 모든 연결 가능성 탐색을 위해선

 [ dfs + 완탐을 활용해 ]
 (1) n 번째 core에 d 방향으로 연결 후
 (2) 다음(n+1) core 연결하기
 (3) n 번째 core에 d 방향으로 연결 취소하기 의 로직을 따라서, dfs를 하면 모든 경우의 수를 탐색할 수 있다.

  제약사항)  최대한 많은 Core에 전원을 연결해도, 전원이 연결되지 않는 Core가 존재할 수 있다.
  * 주의할 점은 n 번째 core 에서 d방향으로 연결 하지 못할 경우, 연결하지 않고 다음 core의 경우로 넘어가게 해야함
  - 이 부분때문에 49번째에서 fail 발생

 ex.  아래 예시 경우 답이 6이 나와야함.
1
5
1 1 1 1 1
1 1 0 0 1
0 0 0 1 1
0 0 0 1 1
1 0 1 1 1

 Q2. 제한 시간안에 가능할지 ? 
 A2. 시간복잡도

최대 코어의 개수는 12개이다. 또한 각 코어는 4방향 또는 연결되지 않을 수 있다.

따라서 O(5^12) = 244,140,625 이지만 전선은 겹칠 수 없고, 가장자리 코어는 이미 전원이 공급됐다는 조건때문에 시간초과가 발생하지 않는다

특이사항

  1. 우선순위 큐를 사용해서 답을 구함.
  2. dfs에 선택된 코어의 개수를 나타내는 select 변수를 추가해줬어야 했다. ( 선택되지 않는 경우도 고려 )
  3. 선택되지 않았을 때, 선택하지 않고 다음 코어로 넘어가는 조건이 필요했다. 

코드

import java.awt.Point;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Scanner;

public class 프로세서연결하기_sw1767_v2 {
	// 연결하지 않는 경우도 생각
	static int[] dr = { -1, 0, 1, 0, 0 };
	static int[] dc = { 0, 1, 0, -1, 0 };
	static int[][] map;
	static int N, Tc;
	static ArrayList<Point> arr = new ArrayList<>();
	static int core_count = 0;
	static PriorityQueue<answer> ans = new PriorityQueue<>();

	public static class answer implements Comparable<answer> {
		int count;
		int sum;

		public answer(int count, int sum) {
			this.count = count;
			this.sum = sum;
		}

		@Override
		public int compareTo(answer o) {
			// TODO Auto-generated method stub
			if (this.count > o.count) {
				return -1;
			} else if (this.count < o.count) {
				return 1;
			} else {
				return this.sum - o.sum;
			}
		}

	}

	public static void dfs(int depth, int select, int Totalsum) {
		//System.out.println("depth: " + depth + " select : " + select + " Tatalsum : " + Totalsum);
		ans.add(new answer(select, Totalsum));

		if (depth >= core_count) {
			return;
		}
		// 4방향 돌면서
		Point cur = arr.get(depth);
		for (int d = 0; d < 4; d++) {
			int nr = cur.x + dr[d];
			int nc = cur.y + dc[d];

			/*
			 * 0 : 지나가지 않은것, 1: 처음 core 위치, 2 : 선 놓은 곳
			 */
			// 다음 위치가 맵 안에 있고, 아무것도 놓여 있지 않는 곳이라면
			if (isIn(nr, nc) && map[nr][nc] == 0) {

				// 그 방향으로 한줄 쭉 놓을 수 있는지 확인하고
				if (isValid(cur, d)) {
					// 2로 채우고
					int sum = fill(nr, nc, d, 2);
					// test
					//print();
					//System.out.println("-------------");
					dfs(depth + 1, select + 1, sum + Totalsum);
					// dfs 한칸 이동
					fill(nr, nc, d, 0);
					// 0으로 다시 채워서 원상복구 해놓기
				} else {
					dfs(depth + 1, select, Totalsum);
				}
			}

		}
	}

	private static void print() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				System.out.print(map[i][j] + " ");
			}
			System.out.println();
		}
	}

	// 다음위치부터
	private static int fill(int nr, int nc, int d, int i) {

		int count = 1;
		map[nr][nc] = i; // 방문처리해놓고
		while (true) {
			// 다음 위치가 테두리라면
			if (nr == 0 || nr == N - 1 || nc == 0 || nc == N - 1) {
				return count;
			} else {
				nr = nr + dr[d]; // 증가
				nc = nc + dc[d]; // 증가
				map[nr][nc] = i; // i로 바꾸기
				count++;
			}
		}
	}

	// 현재 위치에서 d 방향으로 쭉 놓을 수 있니?
	private static boolean isValid(Point cur, int d) {

		int nr = cur.x + dr[d];
		int nc = cur.y + dc[d];
		// 테두리에 닿을 때까지
		while (isIn(nr, nc)) {
			if (map[nr][nc] != 0) {
				return false;
			}
			nr = nr + dr[d];
			nc = nc + dc[d];
		}

		return true;
	}

	private static boolean isIn(int nr, int nc) {

		if (nr >= 0 && nr < N && nc >= 0 && nc < N)
			return true;

		return false;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		Tc = sc.nextInt();

		// 입력 받으면서
		for (int tc = 1; tc <= Tc; tc++) {
			N = sc.nextInt();
			map = new int[N][N];
			core_count = 0;

			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					map[i][j] = sc.nextInt();

					// 벽이 아닌 1의 위치 기억 하기
					if (map[i][j] == 1 && i != 0 && i != N - 1 && j != 0 && j != N - 1) {
						core_count++;
						arr.add(new Point(i, j));

					}
				}
			}

			// 4방향 dfs 돌면서, 한 줄로 코어에 연결할 수 있으면 연결하고 dfs , 다시 원상복구
			dfs(0, 0, 0);

			System.out.println("#" + tc + " " + ans.peek().sum);
			ans.clear();
			arr.clear();
		}

	}
}

 

코드 설명 ( one by one ) - (1) 우선순위 큐를 사용하기 위한 answer 클래스

public static class answer implements Comparable<answer> {
		int count;
		int sum;

		public answer(int count, int sum) {
			this.count = count;
			this.sum = sum;
		}

		@Override
		public int compareTo(answer o) {
			// TODO Auto-generated method stub
			if (this.count > o.count) {
				return -1;
			} else if (this.count < o.count) {
				return 1;
			} else {
				return this.sum - o.sum;
			}
		}

	}

- 최대한 많은 Core 순서 ( 코어의 개수 ( count ) : 내림차순 )  - (  -1 )
+ Core 수 같을경우 전선의 길이합 최소 ( 연결된 전선의 각 개수 ( sum ) : 오름차순 ) - ( 1 )

코드 설명 ( one by one ) - (2) 모든 core 의 수 연결해보기 위한 DFS

public static void dfs(int depth, int select, int Totalsum) {
		//System.out.println("depth: " + depth + " select : " + select + " Tatalsum : " + Totalsum);
		ans.add(new answer(select, Totalsum));

		if (depth >= core_count) {
			return;
		}
		// 4방향 돌면서
		Point cur = arr.get(depth);
		for (int d = 0; d < 4; d++) {
			int nr = cur.x + dr[d];
			int nc = cur.y + dc[d];

			/*
			 * 0 : 지나가지 않은것, 1: 처음 core 위치, 2 : 선 놓은 곳
			 */
			// 다음 위치가 맵 안에 있고, 아무것도 놓여 있지 않는 곳이라면
			if (isIn(nr, nc) && map[nr][nc] == 0) {

				// 그 방향으로 한줄 쭉 놓을 수 있는지 확인하고
				if (isValid(cur, d)) {
					// 2로 채우고
					int sum = fill(nr, nc, d, 2);
					// test
					//print();
					//System.out.println("-------------");
					dfs(depth + 1, select + 1, sum + Totalsum);
					// dfs 한칸 이동
					fill(nr, nc, d, 0);
					// 0으로 다시 채워서 원상복구 해놓기
				} else {
					dfs(depth + 1, select, Totalsum);
				}
			}

		}
	}

 1. 선택된 모든 개수, 연결된 전선 길이의 합을 ans 라는 우선순위큐에 저장한다.
 2. 만약 depth가 core_count ( 가장자리 제외한 코어의 개수 ) 보다 크거나 같다면, 더 이상 볼 필요는 없다.
 3. 현재 depth에 저장된 list를 꺼낸 뒤 4방향 탐색을 시도한다. ( 어디에 연결 될 수 있는지 ? )
 4. 첫 번째 if 문, 시작지점으로 부터 다음에 놓을 자리에 아무것도 놓여있지 않다면 전선을 놓을 수 있지 않겠는가?
 5. 두 번째 if 문, isValid 함수를 통해 현재 위치에서 d 방향 끝까지 전선을 놓을 수 있는지 체크하고
   5 - 1). 2로 채우면서 전선의 길이 합을 반환하도록 fill 메소드를 구현한다.
   5 - 2). 채워진 후에 ( 해당 코어에 D 방향으로 전선을 연결했다는 뜻, 더이상 해당 코어에 머무를 필요가 없지 )
            dfs( depth +1, select +1 , sum + Totalsum ) 을 통해 다음 코어의 경우로 넘어간다.
   5 - 3). 모든 재귀마지막 후에, 다른 방향들도 탐색 해야 하기 때문에 fill ( ~ , 0 ) 0으로 원상복구 해준다.

 6. ( 49번째에서 실패했던 조건문 )
   - 만약 isValid 함수에서 false가 반환되었다면 == d 방향으로 전선을 놓을 수 없다면 ?
   ==> 다음 방향을 고려하는 것이 아닌, 선택하지 않고 다음 코어로 넘어가 전선 작업을 하는 연산이 필요하다.
   전선이 연결되지 않은 코어도 있을 수 있기 때문에!!