SWEA1767_[SW Test 샘플문제] 프로세서 연결하기

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

문제정리

1. 1개의 cell에는 1개의 core 혹은 1개의 전선이 올 수 있다.

2. 맥시노스의 가장 자리에는 전원이 흐르고 있다.

3. core와 전원을 연결하는 전선은 직선으로만 설치가 가능하며, 전선은 교차해서는 안 된다.

4. 맥시노스의 가장자리에 위치한 core는 이미 전원이 연결된 것으로 간주한다.

5. 최대한 많은 core에 전원을 연결하였을 경우, 전선 길이의 합을 구하고자 한다.

단, 여러 방법이 있을 경우, 전선 길이의 합이 최소가 되는 값을 구하라.

문제issue

1. 중복순열로 연결해야하는 core당 4방향을 모두 살펴보면 최악의 경우 4PI12 라서 시간초과가 발생한다.

2. dfs 재귀를 이용

해결흐름

1. 연결해야 하는 core의 위치를 list에 저장한다.

2. dfs

(1) 종료조건 : list를 살펴보는 인덱스가 list의 크기와 같아지면 list에 있는 모든 core를 살펴봤다는 의미이다.

(2) 가지고 다닐 값 : core가 있는 list , list에서 core를 꺼낼 인덱스 , 몇 개의 core를 연결했는가? , 몇 개의 전선?

(3) 복귀 시켜야 할 값 : map

(4) 재귀를 도는 경우 : 뽑은 core가 한 방향으로 전원가 연결 가능할 때

아닌 경우 : 이 문제는 core를 전원에 연결 못 하더라도 재귀를 돌아야 한다. 다만 현재까지 연결한 core의 개수와 전선의 개수를 갱신 하지 않는다.

3. check()에서는 core 한 개와 방향을 받아서 전원과 연결이 가능한지 검사하고 가능하면 2(전선을 의미)로 맵핑한다.

이때, 전선의 개수를 증가시켜서 끝난후 다음 재귀를 돌때 더해준다.

DFS문제issue

DFS 재귀를 이용하여 문제를 풀기 전에 꼭 생각!!

1. 재귀의 종료조건

2. 함수와 함께 가지고 다닐 값

3. return 후에 원상복귀 시켜야 할 값

4. 재귀를 도는 경우와 아닌 경우

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
 
public class Solution {
 
    static class pair {
        int r;
        int c;
 
        public pair(int r, int c) {
            super();
            this.r = r;
            this.c = c;
        }
    }
 
    private static int max_core;
    private static int min_line;
    private static int N;
    private static int[][] map;
 
    public static void main(String[] args) throws Exception {
        // input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int test_case = Integer.parseInt(br.readLine().trim());
        for (int tc = 1; tc <= test_case; tc++) {
            N = Integer.parseInt(br.readLine().trim());
            map = new int[N][N];
            List<pair> core_list = new ArrayList<pair>();
            for (int i = 0; i < N; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine().trim());
                for (int j = 0; j < N; j++) {
                    int number = Integer.parseInt(st.nextToken());
                    map[i][j] = number;
                    if (number == 1 && i > 0 && i < N - 1 && j > 0 && j < N - 1) {
                        core_list.add(new pair(i, j));
                    }
                }
            }
            max_core = Integer.MIN_VALUE;
            min_line = Integer.MAX_VALUE;
            dfs(core_list, 0, 0, 0); // core담은 list , list에서 꺼낼 변수 idx , 연결한 core 개수 core_cnt , 연결한 전선 개수 line_cnt
            System.out.println("#" + tc + " " + min_line);
        } // end of tc
    } // end of main
 
    private static int[] dr = { -1, 0, 1, 0 }; // 상 우 하 좌
    private static int[] dc = { 0, 1, 0, -1 }; // 상 우 하 좌
 
    private static void dfs(List<pair> core_list, int idx, int core_cnt, int line_cnt) {
        // 종료조건 , core_list의 모든 core를 살펴보았다
        if (idx == core_list.size()) {
            // 값 갱신
            if (max_core < core_cnt) {
                max_core = core_cnt;
                min_line = line_cnt;
            } else if (max_core == core_cnt) {
                if (min_line > line_cnt) {
                    max_core = core_cnt;
                    min_line = line_cnt;
                }
            }
            return;
        }
        // core 한 개당 4방향으로 가능한지 살펴본다
        pair p = core_list.get(idx);
        for (int i = 0; i < dc.length; i++) {
            int line_plus = check(p, i); // 몇번재 코어인지와 방향을 던져준다
            // 해당 core가 해당 방향으로 연결이 가능하다
            if (line_plus != -1) {
                dfs(core_list, idx + 1, core_cnt + 1, line_cnt + line_plus);
                // 변경했던 map을 원상복귀 시켜준다
                int r = p.r;
                int c = p.c;
                int dir = i;
                while(true) {
                    r += dr[dir];
                    c += dc[dir];
                    if(r >= 0 && r < N && c >= 0 && c < N) {
                        map[r][c] = 0;
                    } else break;
                }
            }
        }
        dfs(core_list, idx + 1, core_cnt, line_cnt);
    }
 
    private static int check(pair p, int dir) {
 
        int r = p.r;
        int c = p.c;
        boolean flag = false;
        while (true) {
            r += dr[dir];
            c += dc[dir];
            if (r >= 0 && r < N && c >= 0 && c < N) {
                // 전원이랑 연결이 가능하다
                if ((r == 0 || r == N - 1 || c == 0 || c == N - 1) && map[r][c] == 0) {
                    flag = true;
                    break;
                } else if (map[r][c] != 0) {
                    flag = false;
                    break;
                }
                // 전원이랑 연결이 불가능하다
            }
        }
        // 위에서 검사결과 연결이 가능하다
        r = p.r;
        c = p.c;
        int line_plus = 0;
        if (flag) {
            while (true) {
                r += dr[dir];
                c += dc[dir];
                if (r >= 0 && r < N && c >= 0 && c < N) {
                    line_plus++;
                    map[r][c] = 2;
                } else
                    break;
            }
            return line_plus;
        }
        return -1;
    }
} // end of class