프로세서 연결하기

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

풀이

백트래킹으로 가장자리를 제외한 코어들을 선택해 4방향으로 진행하면서 모든 경우의 수를 탐색해 조건에 맞는 정답을 찾으면 된다.

1. 프로세서 방향 선택
2. 방향대로 전선 설치
3. 프로세서 탐색 끝나면 전선 제거

위 순서로 코드를 작성하고 진행하니 정답을 찾았다.

코드

import java.io.*;
import java.util.ArrayList;

public class Solution {
    // 0 상, 1 좌, 2 우, 3 하
    static int[] dx = {-1, 0, 0, 1};
    static int[] dy = {0, -1, 1, 0};
    static int n, m;
    static int[][] board;
    static int maxProcessor = 0;
    static int minLine = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        // write your code here
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int T = Integer.parseInt(br.readLine().trim());
        for (int t = 0; t < T; t++) {
            maxProcessor =0;
            minLine = Integer.MAX_VALUE;
            n = Integer.parseInt(br.readLine().trim());
            board = new int[n][n];

            String[] line;
            for (int i = 0; i < n; i++) {
                line = br.readLine().split(" ");
                for (int j = 0; j < n; j++) {
                    board[i][j] = Integer.parseInt(line[j]);
                }
            }

            ArrayList<Pair> pList = new ArrayList<>();
            for (int i = 1; i < n - 1; i++) {
                for (int j = 1; j < n - 1; j++) {
                    if (board[i][j] == 1)
                        pList.add(new Pair(i, j));
                }
            }
            backTracking(0,0,0,pList);
            bw.write("#"+(t + 1) + " " + minLine + "\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }

    private static void backTracking(int start, int cnt, int line, ArrayList<Pair> pList) {
        if (start == pList.size()) {
            if(maxProcessor < cnt) {
                maxProcessor = cnt;
                minLine = line;
            }
            if(maxProcessor == cnt) {
                minLine = Math.min(line, minLine);
            }
            return;
        }
        for (int i = start; i < pList.size(); i++) {
            Pair p = pList.get(i);
            for (int k = 0; k < 4; k++) {
                int nx = p.x + dx[k];
                int ny = p.y + dy[k];
                if (board[nx][ny] == 0) {
                    int a = drawLine(p.x, p.y, k);
                    if (a != 0) {
                        backTracking(i + 1, cnt + 1, line + a, pList);
                        eraseLine(p.x, p.y, k);
                    } else
                        backTracking(i + 1, cnt, line, pList);
                }

            }
        }
    }

    private static int drawLine(int x, int y, int k) {
        int cnt = 0;
        // 0 상, 1 좌, 2 우, 3 하
        switch (k) {
            case 0:
                for (int i = x - 1; i >= 0; i--) {
                    if (board[i][y] == 0) {
                        board[i][y] = 2;
                        cnt++;
                    } else {
                        for (int j = i + 1; j < x; j++)
                            board[j][y] = 0;
                        return 0;
                    }
                }
                break;
            case 1:
                for (int i = y - 1; i >= 0; i--) {
                    if (board[x][i] == 0) {
                        board[x][i] = 2;
                        cnt++;
                    } else {
                        for (int j = i + 1; j < y; j++)
                            board[x][j] = 0;
                        return 0;
                    }
                }
                break;
            case 2:
                for (int i = y + 1; i < n; i++) {
                    if (board[x][i] == 0) {
                        board[x][i] = 2;
                        cnt++;
                    } else {
                        for (int j = i - 1; j > y; j--)
                            board[x][j] = 0;
                        return 0;
                    }
                }
                break;
            case 3:
                for (int i = x + 1; i < n; i++) {
                    if (board[i][y] == 0) {
                        board[i][y] = 2;
                        cnt++;
                    } else {
                        for (int j = i - 1; j > x; j--)
                            board[j][y] = 0;
                        return 0;
                    }
                }
                break;
        }
        return cnt;
    }

    private static void eraseLine(int x, int y, int k) {
        // 0 상, 1 좌, 2 우, 3 하
        switch (k) {
            case 0:
                for (int i = x - 1; i >= 0; i--) {
                    if (board[i][y] == 2) {
                        board[i][y] = 0;
                    }
                }
                break;
            case 1:
                for (int i = y - 1; i >= 0; i--) {
                    if (board[x][i] == 2) {
                        board[x][i] = 0;
                    }
                }
                break;
            case 2:
                for (int i = y + 1; i < n; i++) {
                    if (board[x][i] == 2) {
                        board[x][i] = 0;
                    }
                }
                break;
            case 3:
                for (int i = x + 1; i < n; i++) {
                    if (board[i][y] == 2) {
                        board[i][y] = 0;
                    }
                }
                break;
        }
    }
}

class Pair {
    int x;
    int y;

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

    @Override
    public String toString() {
        return "Pair{" +
                "x=" + x +
                ", y=" + y +
                '}';
    }
}