개요
구현이 어려웠던 문제
머리로는 이해하겠지만 코드로는 나오지 않았다고 해야할까.
과정이 조금 복잡해서 단계별로 나누어서 구성했다.
문제분석
우리가 구해야하는 것은 최대한 많은 Core에 전원을 연결하였을 경우, 전선 길이의 합이다.
단, 여러 방법이 있을 경우, 전선 길이의 합이 최소가 되는 값을 구해야한다.
즉, 최대한 많은 코어에 전원을 연결하되, 같은 코어를 연결하는 경우 전선 길이가 짧은 경우를 구해야한다는 것.
이말은 즉슨,연결된 코어의 개수와 전선의 길이 둘다 같이 구해주어야 한다는 것이다.
1.외곽에 위치하고 있는 코어는 이미 전기에 연결되어있다. 즉,
구해줄 필요가 없다
2.전선이 교차해서는 안된다. 즉,전선이 수직으로 교차하는 곳으로 지나서는 안된다는 것이다.
그러면 이 문제를 어떻게 구현해야하는지 고민해보자.
우선,외곽에 존재하는 코어를 제외한 나머지의 코어를 저장해놓는다.
이제부터 코어 하나하나를 돌면서 전깃줄을 놓아주도록 하자. 여기에서 하나의 코어에 대한 전깃줄을 모두 이어주어야 하기때문에 dfs를 사용하는 것이 적절하다.
만약 bfs를 사용하게 된다면 교차하는 경우가 발생할 수 있다. 그렇기 때문에 우리는 dfs를 통해서 depth == 코어의 개수가 될때까지 탐색할것이다.
그러면 이제 로직은 간단하게 풀어보자.
어떤 방향으로 전깃줄이 연결될수있을지 모르기 때문에 일단,4방향으로 탐색을 한다.
count 변수를 사용하여 해당 방향으로 직진하다가, 벽이 나오거나 전깃줄을 만나면 반복문을 종료한다.
여기서 주의해야 할 점은 전깃줄을 만나면 count 자체를 초기화 해주어야 한다는 것이다.
왜냐하면 전깃줄을 만난다 = 이 방향으로는 더이상 갈 수 없다는 것 이기 때문이다.
이렇게 되면,아예 갈 수 없는 방향은 count 변수는 항상 0을 유지할것이고, 갈수있는 방향은 count 변수는 0 보다 클 것이다.
이러한 점을 이용하여 count 만큼 전깃줄을 놓아주는 작업을 할 것이다.
여기서 궁금증이 생길 수도 있는게 count 변수를 왜 굳이? 라고 생각할수도 있다.
왜냐하면 진행하면 안되는 방향으로 전깃줄을 놓으면서 가면 되돌려놓기 힘들기 때문이다.
그렇기 때문에 count를 먼저 센 다음 count에 따라 전깃줄을 놓는 경우와 그렇지 않은 경우를 나누어주는 것이다.
만약, count 가 0이어서 전깃줄을 놓지 않을 경우 해당 코어는 더 이상 그 방향으로 갈수없기 때문에 해당 코어를 포기하고 다음 재귀를 탄다.
count가 1 이상일 경우는 어떻게 될까? 해당 코어를 전깃줄에 연결했다는 표시와 동시에 전깃줄의 길이까지 다음 재귀로 넘겨준다.
이러한 경우에는 전깃줄을 놓았기 때문에,재귀를 마치고 돌아오면, count 만큼 전깃줄을 되돌려놓는 작업을 해주어야한다.
내가 말한 로직이 모두 코드에 담겨있다. 이제 코드로 보자
문제풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
/**
* @author onyoo
* @performance
* @category
* @note
* 프로세서 연결하기
* 가장자리 -> 이미 전원이 연결됨
* 겹치지 않게
* 최대한 많은 코어에 전원을 연결했을 때 전선 길이의 합을 구하자
* 단,여러 방법이 있을 경우 전선 길이의 합이 최소가 되는 값을 구하자
* 최단경로를 가지면서,많이 연결해야한다.
* @see https://swexpertacademy.com/main/solvingProblem/solvingProblem.do
* @since 2023-11-06
**/
public class Solution {
static class Core{
int x,y; //코어의 위치
public Core(int x, int y) {
this.x = x;
this.y = y;
}
}
static int T,N;
static int[][] map;
static int maxCore, minLength;
//최대 코어 개수,최소 전깃줄 길이
static ArrayList<Core> cores;
static int[] dx = {0,0,0,1,-1};
static int[] dy = {0,1,-1,0,0};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
T = Integer.parseInt(br.readLine());
for(int t=1;t<T+1;t++){
N = Integer.parseInt(br.readLine());
map = new int[N][N];
maxCore = Integer.MIN_VALUE;
minLength = Integer.MAX_VALUE;
cores = new ArrayList<>();
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());
if(map[i][j] == 0) continue;
if(i == 0 || j == 0 || i == N-1 || j == N-1 ) continue;
cores.add(new Core(i,j));
}
}
dfs(0,0,0);
System.out.printf("#%d %d\n",t,minLength);
}
}
static void dfs(int depth,int core,int length){
//깊이
//현재 몇번째 코어
//전깃줄의 길이
if(depth == cores.size()){
if(core > maxCore){
maxCore = core; // 코어의 개수가 크다면
minLength = length;
}else if(core == maxCore){
if(length < minLength) {
minLength = length;
}
}
return;
}
Core curr = cores.get(depth); // 현재 코어
for(int i=1;i<=4;i++){
//일단 4방향 중 하나의 방향으로 가보자
int count = 0;
int nx = curr.x;
int ny = curr.y;
// 이동하는 좌표
int rx = curr.x;
int ry = curr.y;
// 전기줄을 잇기 위해 가지고 있는 좌표
while(true){
nx += dx[i];
ny += dy[i];
if(nx < 0 || ny < 0 || nx >= N || ny >= N) break;
if(map[nx][ny] == 1) {
count = 0; // 더 이상 전진 할 수 없는 자리이기 때문에 counting 종료
break;
}
count++;
}
//얼마나 이동할 수 있는지 숫자를 센다
//이동한 횟수가 있다면 그 만큼 전선을 채워준다
for(int c = 0; c < count; c++){
rx += dx[i];
ry += dy[i];
map[rx][ry] = 1; // 전기줄을 이어준다
}
if(count == 0) dfs(depth+1,core,length); // 이번 재귀에서는 이 코어는 연결하지 못할 것 같아요 !
else{
dfs(depth+1,core+1,length+count);
rx = curr.x;
ry = curr.y;
for(int c=0;c<count;c++){
rx += dx[i];
ry += dy[i];
map[rx][ry] = 0;
}
}
}
}
}