[SWEA/Java] 1707 : 프로세서 연결하기

 

문제

 

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

SW Expert Academy

 

 

풀이

 

어렵게 생각하면 한없이 어렵게 느껴지는 문제였다. 주의해야 할 점은 Core에 전원이 연결되지 않는 경우가 있다는 점이다.

 

처음에는 Core가 모두 선택됐을 때를 재귀함수의 기저조건으로 설정했는데, 알고보니 Core가 아예 선택되지 않을 수도 있었다. 따라서 부분집합을 사용해서 풀어야 한다.

 

풀이는 다음과 같다.

1. map[][]에 input 값을 받을 때, 가장 바깥쪽 core(이미 연결되어있는 core)를 제외한 core를 ArrayList에 넣는다. (coreList라 칭해주었다)
2. coreList에 있는 core를 꺼내면서 부분집합을 사용해 해당 core를 연결했을 때와 연결하지 않았을 때로 나누어 모든 경우를 구해본다.
3. core를 연결할 때는 4방향으로 모두 놓아야 하는데, 먼저 isAvailable 함수를 통해 해당 방향으로 갔을 때 장애물이 없는지 확인해주고, 가능한 경우 setLine 함수를 사용해 선을 연결한다.
4. 선을 연결한 상태에서 다음 core를 선택하기 위해 재귀호출한다.
5. map을 복구하기 위해 setLine 함수를 재사용하여 선(2로 설정)을 다시 빈칸(0)으로 돌려놓는다.
6. 부분집합 함수의 매개변수로 넣어주었던 index가 coreList.size()와 같아지면 return 한다.
7. 이 때 연결된 core의 개수와 선의 개수를 잘 파악해 정답을 도출한다.

 

 

코드

 

import java.util.ArrayList;
import java.util.Scanner;

public class Solution {
	static int n, max, min, map[][];
	static int[][] dir = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
	static ArrayList<Node> coreList;
	static Scanner sc = new Scanner(System.in);

	public static void main(String[] args) {
		int tc = sc.nextInt(); // test_case 수
		coreList = new ArrayList<>();// 바깥을 제외한 core를 담는 queue
		for (int test_case = 1; test_case <= tc; test_case++) {

			max = 0;
			min = Integer.MAX_VALUE;

			n = sc.nextInt();
			map = new int[n][n];

			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					map[i][j] = sc.nextInt();
					if (map[i][j] == 1) {
						if (i != 0 && i != n - 1 && j != 0 && j != n - 1) {
							coreList.add(new Node(i, j));

						}
					}
				}
			}

			go(0, 0);

			System.out.println("#" + test_case + " " + min);
			coreList.clear();
		}
	}

	private static void go(int index, int cCnt) { // index:부분집합에 고려한 코어 인덱스, cCnt:연결된 코어 개수
		if (index == coreList.size()) {
			int line = CountLine(); // 놓아진 전선의 길이 구하기
			if (max < cCnt) {
				max = cCnt;
				min = line;
			} else if (max == cCnt) {
				if (min > line) {
					min = line;
				}
			}


			return;
		}
		// 코어 선택 전선 놓아보기(4방향으로 놓아보기)
		Node cur = coreList.get(index);
		int x = cur.x;
		int y = cur.y;
		for (int d = 0; d < 4; d++) {
			if (isAvailable(x, y, d)) {
				// 전선 놓기
				setLine(x, y, d, 2);
				// 다음 코어로 넘어가기
				go(index + 1, cCnt + 1);
				// 놓았던 전선 되돌려 놓기
				setLine(x, y, d, 0);
			}
		}
		// 코어 비선택
		go(index + 1, cCnt);
	}

	private static int CountLine() {
		int cnt = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (map[i][j] == 2) {
					cnt++;
				}
			}
		}
		return cnt;
	}

	private static void setLine(int x, int y, int d, int s) {
		int dx = x, dy = y;
		while (true) {
			dx += dir[d][0];
			dy += dir[d][1];
			if (dx < 0 || dy < 0 || dx > n - 1 || dy > n - 1) {
				break;
			}
			map[dx][dy] = s;
		}
	}

	private static boolean isAvailable(int x, int y, int d) {// 해당 방향으로 끝까지 갈 수 있는지 확인
		int dx = x, dy = y;
		while (true) {
			dx += dir[d][0];
			dy += dir[d][1];
			if (dx < 0 || dy < 0 || dx > n - 1 || dy > n - 1) {
				break;
			}
			if (map[dx][dy] != 0) {
				return false; // 코어나 전선이 놓아있어 불가능
			}
		}
		return true;
	}

	private static class Node {
		int x, y;

		Node(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
}

 

 

느낀점

 

• 백준 문제만 풀다가 SWEA 문제를 푸니까 test case를 다시 돌 때마다 변수 초기화와 자료구조 clear 해줘야 한다는 걸 깜빡했다 ㅜㅜㅜ... 
• SWEA와 IDE환경에서의 연습을 많이 해야겠다