(C++) 1767. [SW Test 샘플문제] 프로세서 연결하기

Standard

문제 링크: https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4suNtaXFEDFAUf

예전에 풀어봤던 문제인데, 다른 이유로 (!?) 헤맨 문제.
– 벽에 붙어있는 CPU는 map에만 넣고, 벽에 붙어 있지 않은 CPU는 queue에 목록으로 넣음
– 처음에는 로직을 이상하게 (?) 짜서 DFS 함수를 CPU 별로 한 방향씩 탐색하도록 시키고, 해당 함수에서 CPU가 포함 불가할 때 4가지 방향, 포함 가능할 때 4가지 방향 이런 식으로 뻗어가다 보니….. O(8^n)이 되어버린 이유로 시간 초과가 나옴
– 예전에 했던 코드를 다시 보니 DFS 함수에는 CPU 정보만 넣고, 내부에서 각 방향으로 선 설치가 가능한 경우+설치 안하는 경우 해서 O(5^n)의 알고리즘을 만드니 시간 통과.

– 효율성의 극대화를 위해 매번 DFS 호출할 때마다 전체 맵 복사 대신 해당하는 부분 (CPU 전선이 설치되는 방향)만 백업해서 처리함.
— 좌로 성공->추가하고 다음 단계 혹은 최종이면 CPU갯수/전선 길이 업데이트 
— 우로 성공->추가하고 다음 단계 혹은 최종이면 CPU갯수/전선 길이 업데이트
— 위로 성공->추가하고 다음 단계 혹은 최종이면 CPU갯수/전선 길이 업데이트
— 아래로 성공->추가하고 다음 단계 혹은 최종이면 CPU갯수/전선 길이 업데이트
— 추가하지 않고 다음 단계 혹은 최종이면 CPU갯수/전선 길이 업데이트

#include <iostream>
#include <cstdlib>

using namespace std;

int maxNumCPU = 0, minNumLine = 0;
int CPUListRow[12]; // CPUListRow[12]
int CPUListColumn[12]; // CPUListColumn[12]
int CPUIdx = -1;
int numN = 0;

void process (int** map);
void process_ (int numTry, int lineLength, int succeedCPU, int** map);

int main(int argc, char** argv)
{
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    
    int T = 0;
    cin >> T;

    int** map;
    map = (int**) malloc (12 * sizeof(int*));
    for (int i = 0; i < 12; i++)
        map[i] = (int*)  malloc (12 * sizeof(int));

    for (int test_case = 1; test_case <= T; test_case++) {
        cout << "#" << test_case << ' ';

        cin >> numN;

        maxNumCPU = 0;
        minNumLine = 0;
        CPUIdx = -1;

        for (int r = 0; r < numN; r++) {
            for (int c = 0; c < numN; c++) {
                cin >> map[r];
                // ignore CPUs at edge. They are placed in the map, but don't need to be connected by line
                if (r != 0 && r != numN -1 && c != 0 && c != numN - 1 && map[r] == 1) {
                    CPUIdx++;
                    CPUListRow[CPUIdx] = r;
                    CPUListColumn[CPUIdx] = c;
                }
            }
        }

        process(map);

        cout << minNumLine << '\n';
    }
	
	return 0;
}

void process (int** map) {
    process_(1, 0, 0, map);
}

void process_ (int numTry, int lineLength, int succeedCPU, int** map) {
    int myRow = CPUListRow[numTry - 1];
    int myColumn = CPUListColumn[numTry - 1];

    int backupContent[12] = {0};

    // 1. check left
    int failed = false;
    int thisLineLength = 0;

    // backup
    for (int c = 0; c < numN; c++) 
        backupContent = map[myRow];
    
    for (int c = myColumn - 1; c >= 0; c--) {
        if (map[myRow] == 0) {
            map[myRow] = 2;
            thisLineLength++;
        }
        else { // 1 (other CPU) or 2 (other line)
            failed = true;
            break;
        }
    }

    if (failed == false) {
        if (numTry < CPUIdx + 1) 
            process_(numTry + 1, lineLength + thisLineLength, succeedCPU + 1, map);
        else {
            if (maxNumCPU < succeedCPU + 1) {
                maxNumCPU = succeedCPU + 1;
                minNumLine = lineLength + thisLineLength;
            }
            else if (maxNumCPU == succeedCPU + 1) {
                if (minNumLine > lineLength + thisLineLength)
                    minNumLine = lineLength + thisLineLength;
            }
        }
    } 
    // restore
    for (int c = 0; c < numN; c++) 
        map[myRow] = backupContent;

    // 2. check right
    failed = false;
    thisLineLength = 0;

    // backup
    for (int c = 0; c < numN; c++) 
        backupContent = map[myRow];
    
    for (int c = myColumn + 1; c < numN; c++) {
        if (map[myRow] == 0) {
            map[myRow] = 2;
            thisLineLength++;
        }
        else { // 1 (other CPU) or 2 (other line)
            failed = true;
            break;
        }
    }

    if (failed == false) {
        if (numTry < CPUIdx + 1) 
            process_(numTry + 1, lineLength + thisLineLength, succeedCPU + 1, map);
        else {
            if (maxNumCPU < succeedCPU + 1) {
                maxNumCPU = succeedCPU + 1;
                minNumLine = lineLength + thisLineLength;
            }
            else if (maxNumCPU == succeedCPU + 1) {
                if (minNumLine > lineLength + thisLineLength)
                    minNumLine = lineLength + thisLineLength;
            }
        }
    }

    // restore
    for (int c = 0; c < numN; c++) 
        map[myRow] = backupContent;

    // 3. check up
    failed = false;
    thisLineLength = 0;

    // backup
    for (int r = 0; r < numN; r++)
        backupContent[r] = map[r][myColumn];

    for (int r = myRow - 1; r >= 0; r--) {
        if (map[r][myColumn] == 0) {
            map[r][myColumn] = 2;
            thisLineLength++;
        }
        else { // 1 (other CPU) or 2 (other line)
            failed = true;
            break;
        }
    }

    if (failed == false) {
        if (numTry < CPUIdx + 1) 
            process_(numTry + 1, lineLength + thisLineLength, succeedCPU + 1, map);
        else {
            if (maxNumCPU < succeedCPU + 1) {
                maxNumCPU = succeedCPU + 1;
                minNumLine = lineLength + thisLineLength;
            }
            else if (maxNumCPU == succeedCPU + 1) {
                if (minNumLine > lineLength + thisLineLength)
                    minNumLine = lineLength + thisLineLength;
            }
        }
    }

    // restore
    for (int r = 0; r < numN; r++)
        map[r][myColumn] = backupContent[r];

    // 4. check down
    failed = false;
    thisLineLength = 0;

    // backup
    for (int r = 0; r < numN; r++)
        backupContent[r] = map[r][myColumn];

    for (int r = myRow + 1; r < numN; r++) {
        if (map[r][myColumn] == 0) {
            map[r][myColumn] = 2;
            thisLineLength++;
        }
        else { // 1 (other CPU) or 2 (other line)
            failed = true;
            break;
        }
    }

    if (failed == false) {
        if (numTry < CPUIdx + 1) 
            process_(numTry + 1, lineLength + thisLineLength, succeedCPU + 1, map);
        else {
            if (maxNumCPU < succeedCPU + 1) {
                maxNumCPU = succeedCPU + 1;
                minNumLine = lineLength + thisLineLength;
            }
            else if (maxNumCPU == succeedCPU + 1) {
                if (minNumLine > lineLength + thisLineLength)
                    minNumLine = lineLength + thisLineLength;
            }
        }
    } 
    
    // restore
    for (int r = 0; r < numN; r++)
        map[r][myColumn] = backupContent[r];

    // 5. go without added
    if (numTry < CPUIdx + 1)
        process_(numTry + 1, lineLength, succeedCPU, map);
    else {
        if (maxNumCPU < succeedCPU) {
            maxNumCPU = succeedCPU;
            minNumLine = lineLength;
        }
        else if (maxNumCPU == succeedCPU) {
            if (minNumLine > lineLength)
                minNumLine = lineLength;
        }
    }
}

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.