Q. 1767 자바 : 프로세서 연결하기

 

문제 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4suNtaXFEDFAUf&categoryId=AV4suNtaXFEDFAUf&categoryType=CODE&problemTitle=1767&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

 

 

아래의 단계로 나눠서 풀었던 것으로 기억한다.

 

1. 먼저 벽에 붙어있지 않은 Core들의 좌표를 List에 저장

2. 코어에 전선을 연결하는 방법 상 하 좌 우를 dy, dx 배열을 이용해 구분하고 이를 dfs 함수로 실행

(반환 조건은 CoreList를 모두 탐색했을 경우)

3. 이 때 끝까지 연결 가능한지, 가능하다면 전선을 연결을 표시하고 그 길이를 반환하는 calLineConnect() 함수 사용

4. dfs가 끝나면 연결된 전선을 다시 되돌리는 rollbackLine() 함수 사용

 

처음에는 좀 감이 안잡혔는데 고민을 열심히 해서 이와 같이 풀었고 다행히 맞췄다.

import java.io.BufferedReader;
import java.util.*;

public class Solution {

    private static BufferedReader br;
    static int[][] Board;
    static int[] dy = {0, 1, 0, -1};
    static int[] dx = {1, 0, -1, 0};
    static int N;

    static int max_Cores;
    static int line_length;
    static int Cores_Cnt;
    static List<int[]> Cores;

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int T;
        T=sc.nextInt();

        for(int test_case = 1; test_case <= T; test_case++)
        {
            N = sc.nextInt();
            Cores = new ArrayList<>();
            Board = new int[N][N];
            Cores_Cnt = 0;
            max_Cores = 0;
            line_length = 0;
            for (int i=0; i<N; i++) {
                for (int j = 0; j < N; j++) {
                    int input = sc.nextInt();
                    if (input == 1) {
                        if (i > 0 && i < (N-1) && j > 0 && j < (N-1)) {
                            Cores.add(new int[]{i, j});
                            Cores_Cnt++;
                        }
                    }
                    Board[i][j] = input;
                }
            }

            dfs(0, 0, 0);
            System.out.printf("#%d %d\n", test_case, line_length);
        }
    }

    public static void dfs(int index, int coreCount, int length) {

        if (index == Cores_Cnt) {
            if (coreCount > max_Cores) {
                max_Cores = coreCount;
                line_length = length;
            } else if (coreCount == max_Cores) {
                line_length = Math.min(line_length, length);
            }
            return;
        }

        int curY = Cores.get(index)[0];
        int curX = Cores.get(index)[1];

        for (int j=0; j<4; j++) {
            int curLen = calLineConnect(curY, curX, dy[j], dx[j]);
            if (curLen == 0) dfs(index+1, coreCount, length);
            else {
                dfs(index+1, coreCount+1, length+curLen);
                rollBackLine(curY, curX, dy[j], dx[j]);
            }
        }
    }
    static int calLineConnect(int y, int x, int dy, int dx) {

        int tmpY = y;
        int tmpX = x;
        while (true) {
            tmpY += dy;
            tmpX += dx;
            if (tmpY < 0 || tmpX < 0 || tmpY == N || tmpX == N) {
                break;
            }
            if (Board[tmpY][tmpX] != 0) return 0;
        }

        int cnt = 0;
        while (true) {
            y += dy;
            x += dx;
            if (y < 0 || x < 0 || y == N || x == N) {
                break;
            }
            Board[y][x] = 2;
            cnt++;
        }
        return cnt;
    }

    static void rollBackLine(int y, int x, int dy, int dx) {

        while (true) {
            y += dy;
            x += dx;
            if (y < 0 || x < 0 || y == N || x == N) {
                break;
            }
            if (Board[y][x] == 2) Board[y][x] = 0;
        }
    }
}

ㅣㅣ