SWEA 1767 - 프로세서 연결하기
Updated:
Java
1767 번 - 프로세서 연결하기
문제
삼성에서 개발한 최신 모바일 프로세서 멕시노스는 가로 N개 x 세로 N개의 cell로 구성되어 있다.
Core와 전원을 연결하는 전선은 직선으로만 설치가 가능하며,
전선은 절대로 교차해서는 안 된다.
최대한 많은 Core에 전원을 연결하였을 경우, 전선 길이의 합을 구하고자 한다.
단, 여러 방법이 있을 경우, 전선 길이의 합이 최소가 되는 값을 구하라.
접근 방법
먼저 탐색해야할 코어들을 찾는다.
2차원 배열의 가장자리에는 이미 전원과 연결 되어 있으므로, y , x != 0 인 코어들을 탐색한다.
그러한 코어가 총 k개라고 하자.
이제 k개의 코어를 하나씩 전선을 연결해 본다.
하나의 코어를 [상,하,좌,우]로 전선을 연결하는데, 만약 연결 성공 하였으면 연결 성공한 코어의 수 + 1을 해주고 다음 코어를 탐색한다.
만약 한 방향으로 전선을 연결하다 도중에 전선이나 코어를 만나면 전선을 연결 할 수 없으므로, 다음 방향으로 전선 연결을 시도한다.
4개의 방향으로 전선 연결을 시도하였지만 하나도 성공하지 못했다면, 성공한 코어수는 그대로 주어지고 다음 코어를 탐색한다.
연결 성공한 코어 수 마다 전선 수를 구하는데, 이때 최소의 전선 수를 저장한다.
최대한 많은 Core에 전원을 연결하였을 때의 최소 전선의 수를 구한다.
구현
좌표를 나타내는 Pair클래스를 선언하였다.
맵 가장자리가 아니고 1인 값의 좌표를 ArrayList에 넣어주어 탐색할 코어를 저장하였다.
DFS를 통해 탐색을 시작하였으며, 매개변수로 [코어 인덱스, 연결 성공한 코어의 수]로 주었다.
코어를 하나 선택하여 그 좌표를 얻는다.
해당 좌표에서 상 하 좌 우로 이동하면 전선을 연결하는데, 중간에 장애물을 만나면 전선을 복구하고
연결에 성공하면 다음 코어의 좌표를 얻어 탐색한다.
5
0 0 0 0 0
0 0 1 0 0
0 1 1 1 0
0 0 1 0 0
0 0 0 0 0
위의 예 처럼 제일 중간의 코어 상하좌우에 코어가 있어 아예 연결이 안되는 경우가 있다.
위 방식에선 하나라도 전원 연결에 성공해야지 다음 코어로 넘어가는데, 위 상황에서는 반례가 존재하게 된다.
따라서 예외를 두었는데, 만약 한 코어가 상 하 좌 우에 한번도 연결에 성공하지 못하면, 연결 코어 수는 유지한채, 다음 코어로 고려하도록 추가 하였다.
위의 예에서는 코어의 수는 5개지만, 연결 성공한 코어의 수는 4개이다.
따라서 코어가 연결 성공한 개수 마다 전선 수를 계산하여 배열로 저장한다.
DFS가 끝난 후, 배열에 저장 된 코어 수가 제일 많은 전선 값의 최소를 구한다.
코드
import java.io.*;
import java.util.*;
class Solution {
static int result = Integer.MAX_VALUE, n;
static int[][] arr;
static ArrayList<Pair> core;
static int[] lineNum;
public static void main(String []args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int tc = stoi(br.readLine());
for(int tidx = 1; tidx <= tc; tidx++) {
result = Integer.MAX_VALUE;
n = stoi(br.readLine());
arr = new int[n][n];
core = new ArrayList<>();
for(int i = 0; i < n; i ++) {
st = new StringTokenizer(br.readLine());
for(int j = 0; j < n; j++) {
arr[i][j] = stoi(st.nextToken());
if(i != 0 && j != 0 && i != n - 1 && j != n - 1 && arr[i][j] == 1) {
core.add(new Pair(i,j));
}
}
}
// 전원이 연결 된 코어의 수에 따라 필요한 최소 전선의 수를 저장하는 배열
lineNum = new int[core.size() + 1];
for(int i = 0; i < core.size() + 1; i++) {
lineNum[i] = Integer.MAX_VALUE; // 각각 최솟값을 구해야 하므로 int 최대로 초기화 한다.
}
DFS(0,0);
// 계산이 끝난 후, 가장 전원이 많이 연결 된 코어의 최소 전선의 수를 구해야 하므로 뒤에서 부터 탐색한다.
for(int i = core.size(); i >= 0; i--) {
if(lineNum[i] != Integer.MAX_VALUE) {
result = lineNum[i];
break;
}
}
System.out.println("#" + tidx + " " + result);
}
}
// 전선의 이동을 나타낸다. [상,하,좌,우]
static int[] dy = {-1,1,0,0};
static int[] dx = {0,0,-1,1};
static void DFS(int lv, int CC) { // lv는 탐색하려는 코어의 인덱스, CC는 현재까지 연결 된 코어의 수
// 현재까지의 연결 된 전선의 수를 센다.
int cnt = 0;
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(arr[i][j] == 2)
cnt++;
}
}
// CC는 현재 전원이 연결 된 코어의 수이며, 해당하는 코어 수에 따른 최소 전선의 수로 갱신한다.
lineNum[CC] = Math.min(lineNum[CC], cnt);
// 만약 모든 코어를 탐색 하였으면 DFS를 종료한다.
if(lv == core.size())
return;
// 현재 코어를 하나 뽑는다.
int y = core.get(lv).y;
int x = core.get(lv).x;
boolean isIn = false; // 최소한 한번이라도 전원에 연결 되어 있는지 확인
for(int i = 0; i < 4; i++) {
boolean isOk = true; // 전원(nxn 배열의 외부)에 연결 되었는지 확인
int ny = y;
int nx = x;
// 상 하 좌 우 하나씩 선택하여 전선을 연결한다.
while(true) {
ny += dy[i];
nx += dx[i];
if(ny < 0 || ny == n || nx < 0 || nx == n) { // 전원에 연결이 되었다
break;
}
if(arr[ny][nx] != 0) { // 전선을 연결하는 도중 코어나 전선을 만나면 전선 연결 실패
isOk = false;
break;
}
arr[ny][nx] = 2; // 전선을 연결한다.
}
if(isOk) { // 전원 연결에 성공하였으면, (다음 코어, 연결된 코어의 수 + 1)을 호출
DFS(lv + 1, CC + 1);
isIn = true; // 한번이라도 전원 연결에 성공
}
// 초기화. 전선을 한번 연결한 것을 끊는 작업이다.
int init;
// 상,하로 전선을 연결 하였을 때
if(y != ny) {
// 아래로 전선을 연결 했을 때
if(dy[i] == -1)
init = 1;
else
init = -1;
while(true) {
ny += init;
if(ny == y)
break;
arr[ny][nx] = 0;
}
}
// 좌,우로 전선을 연결 하였을 때
else if(x != nx) {
if(dx[i] == -1)
init = 1;
else
init = -1;
while(true) {
nx += init;
if(nx == x)
break;
arr[ny][nx] = 0;
}
}
}
// 한 번도 전기 선에 닿아 본 적이 없는 경우
// 연결 된 코어 수는 그대로 두고, 다음 코어로 넘어간다.
if(!isIn) {
DFS(lv + 1, CC);
}
}
static class Pair{
int y,x;
Pair(int y, int x){
this.y = y;
this.x = x;
}
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
builder.append("[").append(y).append(", ").append(x).append("]");
return builder.toString();
}
}
static int stoi(String str) {
return Integer.parseInt(str);
}
}
좀더 깔끔한 코드
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[][] map;
private static int n, max, totalcnt, min;
private static ArrayList<int[]> core;
public static void main(String[] args) throws Exception {
System.setIn(new FileInputStream("res/input.txt"));
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int T = stoi(in.readLine());
for (int t = 1; t <= T; t++) {
n = stoi(in.readLine());
totalcnt = 0;
map = new int[n][n];
max = 0;
min = Integer.MAX_VALUE;
core = new ArrayList<>();
for (int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(in.readLine());
for (int j = 0; j < n; j++) {
map[i][j] = stoi(st.nextToken());
if (i == 0 || j == 0 || i == n - 1 || j == n - 1)
continue;
if (map[i][j] == 1) {
core.add(new int[] { i, j });
totalcnt++;
}
}
}
go(0, 0);
System.out.println("#" + t + " " + min);
}
in.close();
}
static int dx[] = { 1, 0, -1, 0 };// 하 우 상 좌
static int dy[] = { 0, 1, 0, -1 };
private static void go(int index, int cCnt) { // index:부분집합에 고려할 코어 인덱스 ,cCnt:연결된 코어 개수
if (index == totalcnt) {
int res = getLenth();// 놓아진 전선의 길이 구하기
if (max < cCnt) {
max = cCnt;
min = res;
} else if (max == cCnt) {
if (res < min)
min = res;
}
return;
}
// 코어 선택 전선 놓아보기(4방향으로)
int[] cur = core.get(index);
int r = cur[0];
int c = cur[1];
for (int d = 0; d < 4; d++) {
if (isAvailable(r, c, d)) {
// 전선놓기
serStatus(r, c, d, 2);
// 다음 코어로 넘어가기
go(index + 1, cCnt + 1);
// 놓았던 전선 되돌려 놓기
serStatus(r, c, d, 0);
}
}
// 코어 비선택
go(index + 1, cCnt);
}
private static int getLenth() {
int sum = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (map[i][j] == 2)
sum += 1;
}
}
return sum;
}
private static void serStatus(int r, int c, int d, int s) {
int nr = r, nc = c;
while (true) {
nr += dx[d];
nc += dy[d];
if (nr < 0 || nr >= n || nc < 0 || nc >= n) {// 전원 연결가능
break;
}
map[nr][nc] = s;
}
}
private static boolean isAvailable(int r, int c, int d) {
int nr = r, nc = c;
while (true) {
nr += dx[d];
nc += dy[d];
if (nr < 0 || nr >= n || nc < 0 || nc >= n) {// 전원 연결가능
break;
} // 전선을 놓으면 2 빈칸 0 코어 1
if (map[nr][nc] >= 1)
return false; // 코어나 전선이 놓아졋다.
}
return true;
}
static int stoi(String s) {
return Integer.parseInt(s);
}
}
총평
난이도
⭐⭐⭐★★
후기
생각이 떠오르는데로 풀었던 문제라 코드가 많이 지저분하다.
의도 하지 않았지만 가지치기도 성공하여 수행 시간이 짧았던 코드이다.
해결까지 대략 1시간 반
개선할 점
강사님께서는 부분 집합으로 해결하였다.
참고
