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

---

문제 설명

생략함

---

풀이

문제에서 하라는 대로 구현하면 되지만, 생각보다 예외처리를 하거나 로직의 순서를 짤 때 애를 꽤 먹었다. 맵을 이용하는 문제이다 보니 널포인터 에러가 자주 일어났고, 재귀를 이용하는 부분에서 논리적 오류가 많이 발생했다.

import java.util.*;
import java.io.*;
 
public class Solution {
    static class Core {
        int i, j;
 
        public Core(int i, int j) {
            super();
            this.i = i;
            this.j = j;
        }
    }
 
    static int[] di = { -1, 0, 1, 0 };
    static int[] dj = { 0, 1, 0, -1 };
    static int N, maxCore, res;
    static int[][] map;
    static ArrayList<Core> cores = null; // 프로세서 좌표 넣을곳
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();
        int T = sc.nextInt();
 
        // start test case
        for (int t = 1; t <= T; t++) {
            N = sc.nextInt();
            map = new int[N][N];
            cores = new ArrayList<>();
 
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    map[i][j] = sc.nextInt();
 
                    if (map[i][j] == 1)
                        cores.add(new Core(i, j));
                }
            } // end input
 
            maxCore = Integer.MIN_VALUE; // 가장 많이 꽂힌 프로세서 수
            plug(0, map, 0); // 첫번째 플러그 꽂기 시작
            sb.append('#').append(t).append(' ').append(res).append('\n');
        } // end test case
        System.out.println(sb);
    }
 
    // cnt: 현재 검사중인 코어 수
    // plugedCore: 연결된 코어 수
    private static void plug(int cnt, int[][] map, int plugedCore) {
        // 기저조건: 결국 모든 플러그 다 꽂음
        if (cnt == cores.size()) {
            // 가장 많은 코어가 꽂혔는가?
            if(plugedCore > maxCore)
                res = Integer.MAX_VALUE; // 가장 많이 프로세서 꽂았을 때의 가장 짧은 전선 길이
            if (plugedCore >= maxCore) {
                maxCore = plugedCore;
                // 가장 짧은 전선 길이를 구해본다
                int sum = 0;
                for (int i = 0; i < N; i++) {
                    for (int j = 0; j < N; j++) {
                        if (map[i][j] == 2)
                            sum++;
                    }
                } // 전선 길이 다 구함
                res = Math.min(res, sum);
            } 
            return;
        }
 
        // 유도파트: 현재 플러그의 네 방향에 꽂을거임 그리고 다음 플러그도 꽂을거임
        int[][] newMap = new int[N][N];
        copy(newMap, map); // 맵 복사: 현재 단계의 상태 저장
        Core nowCore = cores.get(cnt); // cnt번째 코어 검사
 
        // 일단 지금 플러그의 네가지 주변부분에 꽂을수 있는지 좀 봐야겠음
        // 근데 벽에 꽂혀잇음: 다음 프로세서 꽂기 ㄱㄱ 그리고 아무방향으로도 안꽂을것
        int top = nowCore.i + di[0];
        int right = nowCore.j + dj[1];
        int down = nowCore.i + di[2];
        int left = nowCore.j + dj[3];
 
        if (down >= N || top < 0 || right >= N || left < 0) {
            plug(cnt + 1, newMap, plugedCore + 1);
            return;
        }
 
        // 네방향 꽂을 수 있는지 검사
        for (int n = 0; n < 4; n++) {
            int ni = nowCore.i + di[n];
            int nj = nowCore.j + dj[n];
 
            // 1있음: 못꽂음
            if(newMap[ni][nj] != 0) {
                plug(cnt + 1, newMap, plugedCore);
            }
 
            // 꽂을 수 있을 거 같음: 벽까지 꽂을수 있는지 검사하고 전선연결
            if (canPlug(ni, nj, newMap, n)) {
                // 꽂힘 => 다음프로세서 꽂기 ㄱㄱ
                plug(cnt + 1, newMap, plugedCore + 1);
                reset(ni, nj, newMap, n); // 다음방향으로도 꽂아봐야돼서 꽂힌전선 다 뽑음
            } else { // 못꽂음=>다음방향 ㄱㄱ
                continue;
            }
        }
    }
 
    // dir 방향으로 전진하며 벽으로 가볼거임
    static boolean canPlug(int i, int j, int[][] newMap, int dir) {
        /* 기저조건 */
        // 벽을 만남 : 가능!! 전선 꽂으셈
        if (i < 0 || i >= N || j < 0 || j >= N)
            return true;
        // 벽에 못만났는데 더이상 전진할 수가 없음
        else if (newMap[i][j] != 0)
            return false;
 
        // 재귀 실행파트: 다음 방향에 전선을 꽂을 수 있는가?
        if (canPlug(i + di[dir], j + dj[dir], newMap, dir)) {
            newMap[i][j] = 2; // 2는 전선임
            return true; // 이전 재귀에도 꽂을 수 있다는 신호 주기
        }
        return false; // 위에서 꽂을 수 있는 신호 못주면 망한거임
    }
 
    // 전선 꽂은거 되돌리기
    static void reset(int i, int j, int[][] newMap, int dir) {
        while (true) {
            if (i < 0 || i >= N || j < 0 || j >= N)
                break;
            if (newMap[i][j] == 2) {
                newMap[i][j] = 0;
                i += di[dir];
                j += dj[dir];
            }
        }
    }
 
    // 배열 복사
    static void copy(int[][] newMap, int[][] map) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                newMap[i][j] = map[i][j];
            }
        }
    }
}

---

재귀를 이용했는데, 코어를 꽂는 가능한 모든 경우에 대해 생각해야 하다보니 조합, 순열을 떠올랐기 때문이다.
아무튼 맵에서 코어가 발견되면 cores에 넣고, 코어 하나 하나를 plug함수로 꽂아본다.
plug함수에선 cnt번째에 해당하는 코어가 꽂히느냐 마느냐를 결정한다.
그리고 모든 코어에 대한 검사를 마치면 코어가 총 몇 개 꽂혔는지 검사하고, 역대급으로 많이 꽂았으면 전선의 길이를 센다.

꽂히느냐 마느냐를 결정할 때는 canPlug함수를 써서 해당 위치에서 사방으로 끝까지 가본다.
벽에 도달해서 마지막 재귀에서 true를 리턴하면 부모 재귀들이 모두 true를 받게 되므로 그 때 맵에 전선을 반영한다.

전선을 꽂았으면 다음 코어 꽂기의 재귀를 실행한다. 이번 타임의 재귀가 끝나면 지금 코어에서 꽂은 전선을 뽑아버리고 다음 방향으로 꽂을 수 있는지 검사한다.

---

후기

plug부분의 구현 순서? 이걸 생각해내는 데는 많은 시간을 쓰진 않았지만 canPlug와 reset함수를 구현하면서 적잖은 오류에 직면했다.

재귀를 이용했지만 구현 문제이다 보니 내 구현이 잘 될것인지 아닌지에 대한 고민을 많이 해야했다.

구현 문제를 처음 봤을 때 설계를 대충 하지 말고 꼼꼼히 한다음에 코딩을 시작해야 더 빠르게 끝낼 수 있다. 키보드에 손을 먼저 올린다고 먼저 끝나진 않는다. 오히려 디버깅 때문에 더 고통받게 된다.