https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4suNtaXFEDFAUf
🚨 실력이 뛰어나지 않아 코드가 다소 지저분할 수 있습니다! 🚨
문제
삼성에서 개발한 최신 모바일 프로세서 멕시노스는 가로 N개 x 세로 N개의 cell로 구성되어 있다.
1개의 cell에는 1개의 Core 혹은 1개의 전선이 올 수 있다.
멕시노스의 가장 자리에는 전원이 흐르고 있다.
Core와 전원을 연결하는 전선은 직선으로만 설치가 가능하며,
전선은 절대로 교차해서는 안 된다.
초기 상태로는 아래와 같이 전선을 연결하기 전 상태의 멕시노스 정보가 주어진다.
(멕시노스의 가장자리에 위치한 Core는 이미 전원이 연결된 것으로 간주한다.)
최대한 많은 Core에 전원을 연결하였을 경우, 전선 길이의 합을 구하고자 한다.
단, 여러 방법이 있을 경우, 전선 길이의 합이 최소가 되는 값을 구하라.
위 예제의 정답은 12가 된다.
제약 사항
-
7 ≤ N ≤ 12
-
Core의 개수는 최소 1개 이상 12개 이하이다.
-
최대한 많은 Core에 전원을 연결해도, 전원이 연결되지 않는 Core가 존재할 수 있다.
입력
입력의 가장 첫 줄에는 총 테스트 케이스의 개수 T가 주어지며 그 다음 줄부터 각 테스트 케이스가 주어진다.
각 테스트 케이스의 첫 줄에는 N값이 주어지며, 다음 N줄에 걸쳐서 멕시노스의 초기 상태가 N x N 배열로 주어진다.
0은 빈 cell을 의미하며, 1은 core를 의미하고, 그 외의 숫자는 주어지지 않는다.
출력
각 테스트 케이스마다 '#X'를 찍고, 한 칸 띄고, 정답을 출력한다.
(X는 테스트 케이스의 번호를 의미하며 1부터 시작한다.)
풀이
문제를 잘 이해하고 주어진 조건대로 차근차근 구현한다면 크게 어렵진 않다.
다만 까다로운 부분이 꽤 있는 편이다.
- 가능한 경우의 전선은 모두 배치해보는 백트래킹으로 문제를 풀었다.
- 코어가 최대로 많을 때의 최소 전선 길이를 구해야 한다. 즉, 전선 길이는 더 길더라도, 연결한 코어가 더 많다면 새로 갱신해야 한다.
- 코어의 크기가 같다면 전선의 최소 길이를 갱신한다.
- 테두리에 닿아있는 코어는 전선을 연결하지 않아도 이미 연결된 상태이기 때문에 넘어간다.
- 많은 백트래킹이 일어나기 때문에 방문체크에 유의한다. (전선 깔고, 되돌리는 과정)
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Swea1767 {
static int n, maxCore, minLine;
static int[][] map;
static ArrayList<int[]> cores;
static int[] dr = {-1, 1, 0, 0}, dc = {0, 0, -1, 1};
/*
가장자리의 코어는 이미 연결된 상태
'최대'한 많은 코어를 연결했을 때의 '최소' 전선 길이를 구하자.
*/
public static void main(String[] args) throws IOException {
System.setIn(new FileInputStream("src/input.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
StringBuilder sb = new StringBuilder();
int t = Integer.parseInt(br.readLine());
for (int tc = 1; tc <= t; tc++) {
n = Integer.parseInt(br.readLine());
map = new int[n][n];
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] == 1) cores.add(new int[] {i, j});
}
}
maxCore = Integer.MIN_VALUE;
minLine = Integer.MAX_VALUE;
check(0, 0, 0);
sb.append("#").append(tc).append(" ");
sb.append(minLine).append("\n");
}
System.out.println(sb);
}
/*
1. 맨 위, 왼쪽부터 보며 1일 경우 전선을 연결해본다.
1-1. 코어가 0행 || n-1행 || 0열 || n-1열 일 경우 바로 다음 코어로 넘어간다. (전체 코어에 더하고 -> 일단생략)
2. 상하좌우 가능한 방법으로 모두 수행해 본 후 가능할 경우 다음 코어로 백트래킹
3. 마지막 코어까지 연결을 마치면, 전체 코어 개수를 확인하고, 최댓값을 갱신한다.
4. 만약 현재 코어수가 최댓값이라면, 거리의 최솟값을 갱신한다.
*/
static void check(int idx, int coreCnt, int lineCnt) {
// 3. 마지막 코어까지 연결을 마치면,
if (idx == cores.size()) {
// 3-1. 전체 코어 개수를 확인하고, 최댓값을 갱신한다.
if (coreCnt > maxCore) {
maxCore = coreCnt;
minLine = lineCnt;
}
// 4. 만약 현재 코어수가 최댓값이라면, 거리의 최솟값을 갱신한다.
else if (coreCnt == maxCore) {
minLine = Math.min(minLine, lineCnt);
}
return;
}
// 1. 맨 위, 왼쪽부터 보며 1일 경우를 살펴본다.
int[] core = cores.get(idx);
int r = core[0];
int c = core[1];
// 1-1. 현재 코어가 테투리와 닿아 있다면, 다음 코어로 넘어간다.
if (r == 0 || c == 0 || r == n - 1 || c == n - 1) {
check(idx + 1, coreCnt, lineCnt);
}
// 1-2. 닿아있지 않다면, 상하좌우 탐색 진행
else {
for (int i = 0; i < 4; i++) {
boolean flag = false;
int cnt = 0;
int curR = r, curC = c;
int nr, nc;
while (true) {
nr = curR + dr[i];
nc = curC + dc[i];
// 테두리에 닿으면 좋료
if (nc < 0 || nc >= n || nr < 0 || nr >= n) break;
// 빈칸이면 전선 놓기
if (map[nr][nc] == 0) {
map[nr][nc] = 2;
cnt++;
}
// 코어가 있거나, 전선이 있다면 더이상 탐색할 필요 없다
else {
flag = true;
break;
}
curR = nr; curC = nc;
}
// 코어, 전선과 마주치지 않고 무사히 탐색을 끝냈다면, 카운트를 추가해서 다음값으로 넘겨준다
if (!flag) {
check(idx + 1, coreCnt + 1, lineCnt + cnt);
rollback(nr - dr[i], nc - dc[i], i); // 되돌리기
}
// 코어, 전선과 마주쳤다면, 깔았던 전선을 모두 회수한 후 다음 값으로 넘어간다
else {
rollback(nr - dr[i], nc - dc[i], i); // 되돌리기
check(idx + 1, coreCnt, lineCnt);
}
}
}
}
// 되돌리기
static void rollback(int nr, int nc, int i) {
while (map[nr][nc] == 2) {
map[nr][nc] = 0;
nr -= dr[i];
nc -= dc[i];
}
}
}
구현+백트래킹 문제는 정말 번거롭긴 하지만 풀고 나면 정말 뿌듯하다 ㅎㅎ
시간초과에 대한 개념이 아직 부족해서 시간초과가 날까 걱정했는데 다행히 통과했다.
시간초과는 어느 경우에 일어나는지도 알아봐야겠다.
