학부 시절 때 (3-2) – 번외편 (TA)

Standard

대학 전에 CCNA/CCNP 공부를 하고 자격증도 따고 왔으며…
컴퓨터 네트워크 수업도 2학년 때 듣고 A0라는 나쁘지 않은 성적을 가지는 나는….
네트워크 전공 교수님께 발탁(?)당했다.

3학년 2학기 때 3학년 수업인 컴퓨터 네트워크 TA를 했으며…..
2009년도에 1학기 과목으로 처음 열릴 네트워크실습 과목 (4학년 과목)의 첫 TA를 했다.
덤으로 네트워크실습 과목의 교재 집필 보조도 했었고…
(덕분에 나는 네트워크실습을 수강할 수 없었다는 슬픈 이야기)

TA를 하게 되면 과제 채점을 위해서 공부를 다시 하게 됐다.
아무리 답안 가이드가 있어도, 부분 점수라거나 좀 일반적이지 않은 답이라거나 하면 내가 찾아볼 수 밖에 없었고… 질문도 막 들어오고 하니까..?
어디선가 쉽게 다른 사람에게 풀이할 수 있으면 제대로 아는 거라고 하는데, 그러한 것을 훈련하는데 큰 도움이 되었다.

지금 생각해보면 학부생으로써 참 많은 경험을 한 것 같다.
보통 4학년들이 하는 3학년 과목 조교도 그렇고, 대학원생들이 하는 4학년 과목 조교도 그렇고…
사실 네트워크 쪽은 병특을 위해 한 공부였는데.. 병특을 안 가게 되면서 묻혀지나 했는데… 결국 커리어에 큰 영향을 준… 그런게 되어 버렸다.
(21살 때 그런거 어디서 읽어 본 안목 있는 나란 녀석…)

이 영향은 대학원 연구실 컨텍 때도 이어졌는데….
네트워크 하는 연구실로 애초에 좁혀놓고 선택하게 됐다. 그리고 그 중 하나로 왔고… 졸업도 했고… 비록 세부전공은 대학원 와서 달라지긴 했지만…

21살 때의 선택이 대학 와서도, 대학원 와서도, 졸업하고도, 회사 가서도 계속…… 꾸준한 커리어의 밑바탕이 되고 있다. (회사에서 뭐하게 될지는 입사 확정되고 나서…)
다르게 말하면, 씨앗을 잘 심고 가꾸면 그 것이 내 지속적인 전문성이 된다는 것. 나는 그런 면에선 매우 운과 시기를 잘 타고 났다고 생각한다.

(4학년 이야기 하기 전에 뭔가 쓰고 싶어서 3-2편으로..)
(일단 잠이 오므로 후속편은 또 시간나는 대로)

학부 시절 때 (3) – 압축(?) 수강의 3학년

Standard

제목에서도 짐작할 수 있을지 모르겠지만….
조기졸업할 조건을 만들어놓고도 그냥 나는 4년을 다녔다 (…?)
그 이유 중 하나는 대학원 면접 준비였고, 또 다른 하나는 1년 빨리 졸업한다고 뭐 당장 할게 없었기 때문이다.
(3학년 겨울 계절을 두 개 들었으면 조기졸업 가능이었는데… 한 개만 들어서 2학점 모자란 상태로 4학년을 갔다. 그럼 조졸을 포기하고 4학년을 어떻게 살았느냐.. 그건 4편에서!)

3학년이 되기 전, 겨울 계절학기로 C++ 프로그래밍을 수강했다.
뭔가 절대 안 열릴만한 과목이 열렸다기에 망설이지 않았다….
계절학기 답게 숙제의 주기는 참 짧았고, 압축적으로 C++를 배우는 시간이 되었다.
(다른 OOP 언어를 먼저 배우면 헷깔린다는데, 다행히도? 별로 헷깔리진 않았다)

3학년이 되고 “오직 6학기 조기졸업”만을 생각한 나는…….
1학기 때 객체지향설계패턴 (OODP), 알고리즘, OS, DB, 컴파일러, 임베디드프로세서응용 이라는 전공몰빵의 22학점의 삶을 살았다.
(이 중 컴파일러는 4학년 과목이다….. 교수님이 3학년인데 왜 듣냐고 해서 조기졸업하려고 한다 해서 수강 승인을 받았던 기억도..)

3학년이 되니 좀 실험 과목이 생겼다. 임베디드프로세서응용… 이라고 arm프로세서 기반의 실험 보드로 프로젝트 하나 구상해서 짜는 과목이 있다. 리눅스 같은 OS에 의존하는게 아니고, 좀 더 로우레벨에서 레지스터 건든다거나 이런 식으로 짰던 기억이… (실험 과목이 하나쯤은 있어야 학기가 재밌어진다는건 진리인가 봄)
(임베디드프로세서시스템 이라는 다른 과목이 2학기에 있는데, 이건 리눅스 기반으로 하는거..)
OODP야 뭐 자바 응용판…..이었고, 알고리즘은 열심히 따라간 덕에 재밌게 했었고… OS도 재밌었고… DB도 괜찮았고………..
문제는 컴파일러였다. 어디서 ‘컴공과라면 컴파일러는 들어야지’라는 소리를 들어서 호기롭게 신청하기는 했는데… 같이 듣는 사람들은 거의 다 4학년이다.. 그것도 좀 한다 하는 선배들……….
22학점을 들으면서 전공 6개의 과제를 해내야 하는 나와… 그것보단 좀 더 시간 투자가 가능한 선배들…
(돌아보면 이 때부터 밤새서 쫙 하고, 방전되서 아침에 뻗어있는 패턴이 몸에 박힌거 같다….)
이 때의 프로그래밍 경험은 차후에도 꽤 도움이 됐다. 취미로 파서 같이 뭘 분류하는 프로그램 짤 때도 물론이었고….
여담으로 다른 과목 프로젝트 때문에 마지막 선택과제를 포기했더니 A0를 받았다.. (눈물)

눈물겨운 3학년 1학기를 끝내고… 2학기는 좀 널럴하게 수강신청했느냐? 라고 한다면 당연히! 아니었다…
전공을 몰아서 듣는 고통과 쾌감을 같이 즐긴 나는…. (!???) 소프트웨어공학, 웹개발, PL, 운영체제실습, 임베디드시스템프로그래밍, 디지털시스템설계…. 또 전공 6개의 삶을 택했다.
소프트웨어공학이나 웹개발은 뭐 적당히 넘어갔고.. PL도 원래 2-3학년 때 듣는 거니까 크게 힘들진 않았고 (사실 PL듣고 컴파일러 듣는게 학과 커리큘럼이었는데, 그걸 거꾸로 들으니 PL은 참 편했다.)… 임베디드시스템프로그래밍은 응용을 들었었기 때문에 크게 다르진 않았고….
문제는 4학년 과목인 운영체제실습과 처음 생긴 2학년 과목인 디지털시스템설계였다.
운영체제실습은 꽤 어려웠고, 내가 바본가…? 라는 생각을 엄청 하게 만든 첫 과목이었다. 내가 기초가 부족했다 라는걸 참 많이 깨닫게 해줬고, 그 덕에 많이 배웠다. (여담으로 이 과목도 컴파일러와 마찬가지로 쟁쟁한 선배들이 너무 많았다…)
디지털시스템설계는 논리설계실험이 없어지면서 생긴 과목인데, 안 듣고 넘어가기는 아쉬워서 3학년이지만 듣게 되었다. VHDL을 처음으로 접해본 과목인데 이 것도 FPGA로 실제 실험을 하는 과목이라서 꽤 재밌는 과목이었다. (실험 과목은 안 피해가는 나란 사람…)

두 학기 모두 전공이 1개씩 A0고 나머지는 A+이라는 꽤 괜찮았던 성적….을 주었는데, 성적이라는 건 결과물이고 결국 내가 잘 배웠느냐 라는게 중요한데…. 정신 없기는 했지만 그만큼 짧은 시간에 많이 성장했다고는 생각한다.
(1학기는 컴파일러가 A0, 2학기는 소공이 A0… 이 교수님께 들은 4개 수업 중 2개는 A+, 2개는 A0……..
사실 이 교수님의 수업은 A0까지는 어렵진 않지만, A+을 받기 위해선 완벽을 기해야한다는 말을 들어왔던 터라……. 크게 아쉽진 않았다. 두 개라도 받은게 어디야…)

(4편 예고)
이렇게 빡시게 3학년을 보내서 졸업학점을 2학점만 남긴 나는…
4학년 때 뭐하지 고민을 하게 되는데…….
(하지만 고민할 필요는 없었죠..?)

학부 시절 때 (2) – 컴공과의 환상이 깨짐

Standard

물론 컴공과가 컴퓨터 조립 배우는 과가 아니라는 것은 진작 알고 있어서 이게 환상은 아니었고…
나는 구체적으로 뭔가 하는 걸 배우는 게 컴공과 라고 생각했는데.. (뭔가 나 이거 할 줄 알아 하는 멋있는 모습…?)
컴공과에 배워야 할 이론이 아주 많다는 것이 나에겐 환상이 깨지는 것이었다.

1학년 때 C 프로그래밍를 할 때는 몰랐는데..
2학년이 되고 1학기 때 데이터 구조 (Data Structures)와 논리 설계 (Logic Design)를 들으면서 이게 뭐지…? 라는 생각을 많이 한 것 같다.
이게 내가 알고 있는 내용들이랑 무슨 상관이지..? 라는 의문도 꽤 가졌었고…
그래도 커리큘럼이니 해야지 뭐.. 정도로 생각하고 공부를 했던 것 같다.

그래도 재밌게 공부하기는 했었다. Linked list가 뭐고, stack/queue가 뭐고, graph가 뭐고… 이런 개념들을 새롭게 알아간다는 자체에 재미를 느꼈다. (??)
논리 설계는 크게 어렵지는 않았던 것 같다. (다만, 증명은… 머리가… 아팠다…)

2학기가 되고, 나는 무슨 깡으로 그랬는지는 모르겠지만…
당시 3학년 전공인 컴퓨터네트워크나 윈도우프로그래밍 같은 과목을 넣는 미친 짓(?)을 했었다.
이 때 들은 전공이 이산수학, 자바, 컴퓨터구조, 윈도우 프로그래밍, 컴퓨터네트워크 (회로이론2……도 있긴 하지만?) 이었으니 그렇게 낮은 로드는 아니었던거 같다.
근데 역설적으로 전공에 둘러쌓인 삶을 사니 수업이나 과제하는거 자체는 엄청 재밌었던 기억이 난다. (???)
이산수학이야 애초에 엄청 어려운 과목은 아니었으니 괜찮았고, 자바는 최초로 접해본 OOP였는데 뭔가 신개념의 언어라 재밌게 배운 기억이……
윈도우프로그래밍은 WinAPI로 주어진 과제를 하는.. OS의 실습 버전? 이었다. OS를 안 듣고 하느라 쉽지는 않았지만 어찌어찌 잘 넘기긴 했었고…
컴퓨터네트워크는 애초에 CCNA/CCNP 공부 좀 하고 와서 크게 어렵진 않았다. (그리고 2학년 때 이 것을 수강한 건…. 3학년 때 이 과목 (3학년 과목….이다) TA를 하게 된 특이한 경험의 발판이 되었다)
컴퓨터구조가 개인적으로는 헬파티? 였는데… 그 중요성에 비해 내가 그렇게 잘 따라가지 못했던 슬픈 기억이 있다. (이 컴구는 대학원 QE (박사자격시험) 때도 유일한 탈락 과목으로 QE를 한 번 더 치게 만들었던 아픈 기억이 있다…)

그래도 윈도우프로그래밍 덕에 2학년이 지루하지는 않았다. 이론 범벅인 2학년 과목에서 삶의 긴장감(?)을 놓을 수 없었으니….?

(3편 예고)
뭔가 이렇게 3학년 같은? 2학년이 지나가고….
전공에 재미들린 나는… 조기졸업을 노리고 3+4학년 수업을 1년만에 듣기 프로젝트를 수행하게 되는데….

학부 시절 때 (1) – 컴공과에 오게 된 계기?

Standard

(제목은 나중에 바꿀 수도 있음)
(애초에 두서 없는 시리즈니 짜임새를 기대하는건…….)

진로 고민은 누구에게나 있는 법이다. 그 정도는 차이가 있겠지만…..
대학을 컴공과로 오게 된 건 어떻게 보면 “컴퓨터라는 게 너무 익숙해서”가 나에겐 답이었다.
어렸을 때부터 컴퓨터 게임은 다들 해 봤을 것이고…

중학교 때 컴퓨터 잡지를 접하게 되면서 리눅스라는 세계를 알게 됐다.
윈도우에 길들여진 일반인에게 리눅스는 뭔가 신비의 세계처럼 다가왔었고…
당시에는 뭔가 윈도우 대신 쓸 수 있는 데스크탑 환경을 제공하는 무료 OS? 이런 이미지였다. 당시엔 redhat linux 배포판 시디가 들어 있었던 기억이….

물론 뭔가 제공은 하지만, 윈도우를 이길 수는 없었기에…… 잠깐 깔아보고 응? 하고 다시 윈도우 깔고……
(나중에는 좀 스마트하게 듀얼부팅으로 깔고 리눅스 날리고……가 되었다)
그렇게 리눅스는 뭔가 스쳐 지나간 존재였지만, 그래도 꾸준히 두들겨 보는 곳이 되었다. (지금이야 아주 익숙하지만..!?)

고등학교 때는 야자만으로도 바빠서 그렇게 많이 도전해 보지는 못했다.
아, 고등학교 때 특별활동이 웹 프로그래밍 (2001-2003년도에 PHP라…..니? 당시는 cgi라는게 많이 쓰이던 시절이다.)이라 웹페이지를 넘어 뭔가 게시판 같은 것을 따라서 만들어 본 기억은 있다. (무슨 웹서버를 썼는지까지는 기억이 안나는데 아마 apm (apache/php/mysql)이었겠지..?)
리눅스도 그렇고 php도 그렇고 뭔가 신비해 보이는 것에 겁없이 (?) 덤벼들었던 것 보면 호기심과 모험심이 강했나 보다.

그렇게 고등학교 시절은 지나가고, 대학에 가기 전까지 2년간의 수험 생활이 있었다. 물론 재수/삼수 할 때 딱히 뭘 손대보진 못했고…
삼수 끝나고 대학 가기 전까지 병특을 대비해야지(!)라는 대의를 가지고 MCSE/CCNA/CCNP 자격증을 위해 학원을 다니게 되었다.
(사실 내가 어떤 기준으로, 어떤 정보력으로 저 자격증들을 선택했는진 기억이 안 난다….)
MCSE야 윈도우 서버에 관련된 이야기라 그냥 좀 신기한 정도이고, CCNA/CCNP가 네트워크 쪽에 대한 지식을 처음 접하는 것이기도 했고 장비도 처음 다뤄보고 해서 신기한게 많았다. 21살의 청년에게 수능 끝나고 무료한 시기에 이 자격증 공부는 참 흥미로울 수밖에 없었던 건가.
(그리고 뒤돌아보면 이 때의 경험이 대학교와 대학원 전공까지 영향을 끼쳤다)

대학을 갈 때까지 온갖 스펙타클한 이야기가 있지만, 한 줄로 요약하면 다행히도 수능을 네 번 치는 불상사는 없이 대학을 가긴 갔다.
(정시 추합 기간도 지나고 아예 추가모집 기간으로 따로 뽑는 전형에서 40:1 정도의 경쟁률을 뚫고 붙어버린 나란 사람…)
그럼 다시 컴공과 계기로 돌아와서…
내가 온 한동대학교라는 곳은 1학년 2학기가 끝나고 2학년이 되기 전에 자기가 갈 전공을 자유롭게 고르는 곳이다. (무전공 입학.. 지금은 다른데들도 좀 하고 있긴 하지만?)
보통 그냥 중고등학교 공부만 하다 대학 와서 전공을 고민하는 사람들에 비해서, 리눅스와 php와 네트워크 자격증 쪽의 백그라운드를 들고 온 나란 사람은 아주 자연스럽게 컴공을 고르고 있었다. (다른 쪽은 1의 고민도 안 하고 전산전자공학부를 클릭하고 있었던 나란 사람…)
즉 정리하면, 그냥 익숙해서 고른게 컴공과…!?

(2편 예고)
그렇게 익숙한 환경에 길들여진 선택을 한 나는….
컴공과는 내가 알던 것과 다르다는 것을 너무나 일찍 깨닫게 되는데…..ㅠㅠ

여기다 써 보려고 하는 이야기.

Standard

박사 졸업을 겨우 (?) 하게 된 마당에..
학부 때나 대학원 때 기억에 남는 에피소드들이 있으면 써 볼까 함.

그 외의 이야기도 생각 나는게 있다면..?!

(C++) 2112. [모의 SW 역량테스트] 보호 필름

Standard

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

분명 이전에 풀었던 문젠데, 시간 초과가 또 떠서 당황함.  분명 로직은 별로 차이 안 나는데….
– 처음에 통과 가능한지 확인해서 가능하면 바로 통과
– 통과 불가능하면, 맨 윗줄부터 한 줄씩 ‘A로 바꿈->테스트해서 통과하면 끝/아니면 다음 줄로 넘어감->B로 바꿈->테스트해서 통과하면 끝/아니면 다음 줄로 넘어감->아무것도 안 바꿈->테스트 해서 통과하면 끝/아니면 다음 줄로 넘어감’ 하도록 구현.
– 분명 로직은 잘못되지 않았는데 시간 초과가 떠서.. 고민 좀 하다가 ‘이미 구한 최소 약품 횟수를 넘어가는 경우가 나오면 바로 종료’하는 식으로 바운드를 만들었더니 통과. 1.2초였나..? (자바 때는 3.2초 정도 걸렸음… 응!?)

#include <iostream>

using namespace std;

int minModificationNum = 13 + 1;
int map[13][20] = {{0}}; // D (row), W (column) 

void process(int numD, int numW, int numK);
void process_(int depth, int numProcessed, int numD, int numW, int numK);
bool checkPass(int numD, int numW, int numK);

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

    //freopen("input.txt", "r", stdin);

    int T = 0;
    cin >> T;

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

        int numD = 0, numW = 8, numK = 3;
        cin >> numD >> numW >> numK; // K: threshold to pass

        minModificationNum = 13 + 1;

        // value 0: A, 1: B
        for (int r = 0; r < numD; r++) {
            for (int c = 0; c < numW; c++) {
                cin >> map[r];
            }
        }

        // check first it can be passed without modification
        bool passed = checkPass(numD, numW, numK);

        if (passed == true)
            cout << 0 << '\n';
        else {
            process(numD, numW, numK);
            cout << minModificationNum << '\n';
        }
    }
}

void process(int numD, int numW, int numK) {
    int backup[20] = {0};

    int theRow = 0;
    for (int i = 0; i < numW; i++)
        backup[i] = map[theRow][i];

    // first row changed to A
    for (int i = 0; i < numW; i++)
        map[theRow][i] = 0;

    if (checkPass(numD, numW, numK) == true) {
        if (minModificationNum > 1)
            minModificationNum = 1;

        for (int i = 0; i < numW; i++)
            map[theRow][i] = backup[i];

        return;
    }
    else 
        process_(theRow + 1, 1, numD, numW, numK);

    // first row changed to B
    for (int i = 0; i < numW; i++)
        map[theRow][i] = 1;

    if (checkPass(numD, numW, numK) == true) {
        if (minModificationNum > 1)
            minModificationNum = 1;

        for (int i = 0; i < numW; i++)
            map[theRow][i] = backup[i];

        return;
    }
    else 
        process_(theRow + 1, 1, numD, numW, numK);

    // first row not changed
    for (int i = 0; i < numW; i++)
        map[theRow][i] = backup[i];

    if (checkPass(numD, numW, numK) == true) {
        if (minModificationNum > 0)
            minModificationNum = 0;
        return;
    }
    else 
        process_(theRow + 1, 0, numD, numW, numK);
}

void process_(int depth, int numProcessed, int numD, int numW, int numK) {
    if (depth == numD)
        return;
    if (numProcessed >= minModificationNum)
        return;

    int backup[20] = {0};

    for (int i = 0; i < numW; i++)
        backup[i] = map[depth][i];

    // first row changed to A
    for (int i = 0; i < numW; i++)
        map[depth][i] = 0;
    
    if (checkPass(numD, numW, numK) == true) {
        if (minModificationNum > numProcessed + 1)
            minModificationNum = numProcessed + 1;

        for (int i = 0; i < numW; i++)
            map[depth][i] = backup[i];

        return;
    }
    else
        process_(depth + 1, numProcessed + 1, numD, numW, numK);

    // first row changed to B
    for (int i = 0; i < numW; i++)
        map[depth][i] = 1;

    if (checkPass(numD, numW, numK) == true) {
        if (minModificationNum > numProcessed + 1)
            minModificationNum = numProcessed + 1;

        for (int i = 0; i < numW; i++)
            map[depth][i] = backup[i];

        return;
    }
    else
        process_(depth + 1, numProcessed + 1, numD, numW, numK);

    // first row not changed
    for (int i = 0; i < numW; i++)
        map[depth][i] = backup[i];

    if (checkPass(numD, numW, numK) == true) {
        if (minModificationNum > numProcessed)
            minModificationNum = numProcessed;

        return;
    }
    else
        process_(depth + 1, numProcessed, numD, numW, numK);
}

bool checkPass(int numD, int numW, int numK) {
    bool passed = true;
    for (int c = 0; c < numW; c++) {
        int current = map[0];
        int count = 1;

        for (int r = 1; r < numD; r++) {
            if (current == map[r]) {
                count++;
                if (count == numK) // already passed
                    break;
            }
            else {
                current = map[r];
                count = 1;
            }
        }

        if (count < numK) {
            passed = false;
            break;
        }
    }

    return passed;
}

(C++) 2105. [모의 SW 역량테스트] 디저트 카페

Standard

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

예전에도 풀기는 했는데.. 예전에는 생길 수 있는 경로 유형을 다 list로 저장해서 처리했다면, 이번에는 정석으로 DFS로 풀었음.
– 네 모서리 점은 대각선으로 한 바퀴 돌아올 수 없으므로 제외
– 나머지 점은 LD (왼쪽 아래 대각선), RD (오른쪽 아래 대각선), RU (오른쪽 위 대각선), LU (왼쪽 위 대각선) 네 가지 중 가능한 경우에 한해 process_ 함수 호출됨
– 이 경우 한 바퀴를 잘 돌아오는지 확인하기 위해 LDAvail, RDAvail, RUAvail, LUAvail 변수를 함수에 담고 있다. 각각 해당 방향으로 전환한 적이 있는지 체크 (있으면 1, 없으면 0)한다. 처음에 process()에서 호출할 때 처음 정한 방향은 0, 나머지는 1로 호출됨.
– LDRUCnt는 / 대각선 (왼쪽 아래, 오른쪽 위), LURDCnt는 \ 대각선 (왼쪽 위, 오른쪽 아래) 방향으로 이동한 횟수를 기록. (아래 방향은 +1, 윗 방향은 -1)
이 변수들은 처음에 이동한만큼만 나중에 돌아올 수 있도록 처리하기 위함. LD/RU 혹은 LU/RD 중 나중에 선택된 방향의 경우 해당 변수가 0이 되면 무조건 방향 전환을 시킴.
– 기본적으로 호출될 때 해당 좌표의 디저트는 먹는 것으로 처리하고, 이후 다음 좌표 (해당 좌표+주어진 방향으로 계산) 를 기준으로 이동할 수 있는 방향들을 다 계산해서 함수를 recursive로 호출. 방향이 이상하게 이동하는 것을 막기 위해, 위에서 말한 [LD/RD/RU/LU]Avail 변수들이 사용됨. (한 번 간 방향으로 또 가지 못하게 하기 위해서)

#include <iostream>

using namespace std;

int map[20][20] = {{0}};
int containsNumber[100 + 1] = {0};

int maxDessert = 0;

void process(int size);
void process_(int numTry, int row, int column, int direction, int LDAvail, int RDAvail, int RUAvail, int LUAvail, int LDRUCnt, int LURDCnt, int size);

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

    int T = 0;
    cin >> T;

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

        maxDessert = -1;

        int numN = 0;
        cin >> numN; // map size

        // map construction
        for (int r = 0; r < numN; r++)
            for (int c = 0; c < numN; c++) 
                cin >> map[r];

        process(numN);
        if (maxDessert > 0)
            cout << maxDessert << '\n';
        else
            cout << -1 << '\n';
    }
}

void process(int size) {
    for (int r = 0; r < size; r++) {
        for (int c = 0; c < size; c++) {
            // 4 corner points cannot be the start point
            if ((r == 0 &amp;&amp; c == 0) || (r == 0 &amp;&amp; c == size - 1) || (r == size - 1 &amp;&amp; c == 0) || (r == size - 1 &amp;&amp; c == size - 1))
                continue;

            // LD (left-down) <v
            if (r != size - 1 &amp;&amp; c != 0)
                process_(1, r, c, 0, 0, 1, 1, 1, 0, 0, size);

            // RD (right-down) v>
            if (r != size - 1 &amp;&amp; c != size - 1)
                process_(1, r, c, 1, 1, 0, 1, 1, 0, 0, size);

            // RU (right-up) ^>
            if (r != 0 &amp;&amp; c != size - 1)
                process_(1, r, c, 2, 1, 1, 0, 1, 0, 0, size);

            // LU (left-up) <^
            if (r != 0 &amp;&amp; c != 0)
                process_(1, r, c, 3, 1, 1, 1, 0, 0, 0, size);
        }
    }
}

// direction (LD: 0, RD: 1, RU: 2, LU: 3)
void process_(int numTry, int row, int column, int direction, int LDAvail, int RDAvail, int RUAvail, int LUAvail, int LDRUCnt, int LURDCnt, int size) {
    int thisDessert = map[row][column];

    if (containsNumber[thisDessert] == 0) { // can eat this dessert
        containsNumber[thisDessert] = 1;

        int nextRow = row;
        int nextColumn = column;

        int LDRUCnt_ = LDRUCnt;
        int LURDCnt_ = LURDCnt;

        // move to next location
        switch (direction) {
            case 0: // LD
                nextRow++;
                nextColumn--;
                LDRUCnt_++;
            break;
            case 1: // RD
                nextRow++;
                nextColumn++;
                LURDCnt_++;
            break;
            case 2: // RU
                nextRow--;
                nextColumn++;
                LDRUCnt_--;
            break;
            case 3: // LU
                nextRow--;
                nextColumn--;
                LURDCnt_--;
            break;
        }

        // came back to initial position
        if (LDRUCnt_ == 0 &amp;&amp; LURDCnt_ == 0) {
            if (maxDessert < numTry)
                maxDessert = numTry;
        }
        else {
            // check if it can go further with other direction
            switch (direction) {
                case 0: // LD
                    // keep LD
                    if (nextRow < size - 1 &amp;&amp; nextColumn > 0) { // it can go
                        if ((RUAvail == 0 &amp;&amp; LDRUCnt_ == 0) == false) // if this is third/fourth direction, limit the number of movement to that of first/second direction
                            process_(numTry + 1, nextRow, nextColumn, 0, LDAvail, RDAvail, RUAvail, LUAvail, LDRUCnt_, LURDCnt_, size);
                    }
                    // to LU
                    if (LUAvail == 1 &amp;&amp; nextRow > 0 &amp;&amp; nextColumn > 0) { // it can go
                        if ((RDAvail == 0 &amp;&amp; LURDCnt_ == 0) == false)
                            process_(numTry + 1, nextRow, nextColumn, 3, LDAvail, RDAvail, RUAvail, 0, LDRUCnt_, LURDCnt_, size);
                    }
                    // to RD
                    if (RDAvail == 1 &amp;&amp; nextRow < size - 1 &amp;&amp; nextColumn < size - 1) { // it can go
                        if ((LUAvail == 0 &amp;&amp; LURDCnt_ == 0) == false)
                            process_(numTry + 1, nextRow, nextColumn, 1, LDAvail, 0, RUAvail, LUAvail, LDRUCnt_, LURDCnt_, size);                
                    }
                    break;
                case 1: // RD
                    // keep RD
                    if (nextRow < size - 1 &amp;&amp; nextColumn < size - 1) { // it can go
                        if ((LUAvail == 0 &amp;&amp; LURDCnt_ == 0) == false)
                            process_(numTry + 1, nextRow, nextColumn, 1, LDAvail, RDAvail, RUAvail, LUAvail, LDRUCnt_, LURDCnt_, size);
                    }
                    // to LD
                    if (LDAvail == 1 &amp;&amp; nextRow < size - 1 &amp;&amp; nextColumn > 0) { // it can go
                        if ((RUAvail == 0 &amp;&amp; LDRUCnt_ == 0) == false)
                            process_(numTry + 1, nextRow, nextColumn, 0, 0, RDAvail, RUAvail, LUAvail, LDRUCnt_, LURDCnt_, size);
                    }
                    // to RU
                    if (RUAvail == 1 &amp;&amp; nextRow > 0 &amp;&amp; nextColumn < size - 1) { // it can go
                        if ((LDAvail == 0 &amp;&amp; LDRUCnt_ == 0) == false)
                            process_(numTry + 1, nextRow, nextColumn, 2, LDAvail, RDAvail, 0, LUAvail, LDRUCnt_, LURDCnt_, size);
                    }
    
                    containsNumber[thisDessert] = 0; // restore
                    break;
                case 2: // RU
                    // keep RU
                    if (nextRow > 0 &amp;&amp; nextColumn < size - 1) { // it can go
                        if ((LDAvail == 0 &amp;&amp; LDRUCnt_ == 0) == false)
                            process_(numTry + 1, nextRow, nextColumn, 2, LDAvail, RDAvail, RUAvail, LUAvail, LDRUCnt_, LURDCnt_, size);
                    }
                    // to LU
                    if (LUAvail == 1 &amp;&amp; nextRow > 0 &amp;&amp; nextColumn > 0) { // it can go
                        if ((RDAvail == 0 &amp;&amp; LURDCnt_ == 0) == false)
                            process_(numTry + 1, nextRow, nextColumn, 3, LDAvail, RDAvail, RUAvail, 0, LDRUCnt_, LURDCnt_, size);
                    }
                    // to RD
                    if (RDAvail == 1 &amp;&amp; nextRow < size - 1 &amp;&amp; nextColumn < size - 1) { // it can go
                        if ((LUAvail == 0 &amp;&amp; LURDCnt_ == 0) == false)
                            process_(numTry + 1, nextRow, nextColumn, 1, LDAvail, 0, RUAvail, LUAvail, LDRUCnt_, LURDCnt_, size);
                    }

                    break;
                case 3: // LU
                    // keep LU
                    if (nextRow > 0 &amp;&amp; nextColumn > 0) { // it can go
                        if ((RDAvail == 0 &amp;&amp; LURDCnt_ == 0) == false)
                            process_(numTry + 1, nextRow, nextColumn, 3, LDAvail, RDAvail, RUAvail, LUAvail, LDRUCnt_, LURDCnt_, size);
                    }
                    // to LD
                    if (LDAvail == 1 &amp;&amp; nextRow < size - 1 &amp;&amp; nextColumn > 0) { // it can go
                        if ((RUAvail == 0 &amp;&amp; LDRUCnt_ == 0) == false)
                            process_(numTry + 1, nextRow, nextColumn, 0, 0, RDAvail, RUAvail, LUAvail, LDRUCnt_, LURDCnt_, size);
                    }
                    // to RU
                    if (RUAvail == 1 &amp;&amp; nextRow > 0 &amp;&amp; nextColumn < size - 1) { // it can go
                        if ((LDAvail == 0 &amp;&amp; LDRUCnt_ == 0) == false)
                            process_(numTry + 1, nextRow, nextColumn, 2, LDAvail, RDAvail, 0, LUAvail, LDRUCnt_, LURDCnt_, size);
                    }

                    break;
            }
        }
        containsNumber[thisDessert] = 0; // restore
    }
}

(C++) 1953. [모의 SW 역량테스트] 탈주범 검거

Standard

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

문제 자체는 어렵지 않다. BFS 로 풀면 됨.
– 시작 위치 (맨홀 위치)부터 queue에 넣으면 됨. (시간 정보도 필요)
– queue에서 하나씩 dequeue하면서 좌우상하 위치로 도달 가능한지 (+방문한 적이 없는가) 체크하면서 도달 가능하면 visited mark하고 시간 1 추가해서 enqueue 
(dequeue할 때마다 도달가능한 곳 카운트 1씩 증가)
– 단, enqueue할 때 시간이 넘어간 경우 enqueue하지 않음
– queue에서 나온 후,   도달가능한 곳 카운트 해놓은 것 출력

#include <iostream>
#include <cstdlib>

using namespace std;

int main(int argc, char** argv)
{
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    
    //freopen("input.txt", "r", stdin);

    int T = 0;
    cin >> T;

    int map[50][50] = {0};
    int visited[50][50] = {0};
    int queueR[50*50] = {0};
    int queueC[50*50] = {0};
    int queueT[50*50] = {0};

    for (int test_case = 1; test_case <= T; test_case++) {
        int numN = 0, numM = 0, numR = 0, numC = 0, numL = 0;
        cin >> numN >> numM; // map size (row: N, column: M)
        cin >> numR >> numC; // loc of manhole (R, C)
        cin >> numL; // time elapsed after escape

        // add pipe information
        int numArrived = 0;
        for (int r = 0; r < numN; r++) 
            for (int c = 0; c < numM; c++) 
                cin >> map[r];

        for (int r = 0; r < numN; r++) 
            for (int c = 0; c < numM; c++) 
                visited[r] = 0;
        
        int queueFront = -1;
        int queueRear = -1;

        // first enqueue starting point
        if (queueFront == -1)
            queueFront = 0;

        queueRear++;
        queueR[queueRear] = numR;
        queueC[queueRear] = numC;
        queueT[queueRear] = 1;
        visited[numR][numC] = 1;

        // while the queue is not empty
        while (queueFront != -1 &amp;&amp; queueFront <= queueRear) {
            // dequeue
            int myRow = queueR[queueFront];
            int myColumn = queueC[queueFront];
            int myTime = queueT[queueFront];
            queueFront++;

            //cout << myRow << '/' << myColumn << ' ' << myTime << '\n';
            numArrived++;

            // left, right, up, down
            int rowPair[4] = {0, 0, -1, 1};
            int columnPair[4] = {-1, 1, 0, 0};

            for (int i = 0; i < 4; i++) {
                int newRow = myRow + rowPair[i];
                int newColumn = myColumn + columnPair[i];

                // out of array, don't go further
                if (newRow < 0 || newRow > numN - 1 || newColumn < 0 || newColumn > numM - 1)
                    continue;

                // already visited, don't need to check more than once
                if (visited[newRow][newColumn] == 1)
                    continue;

                // can't go beyond time limit 
                if (myTime == numL)
                    continue;

                switch (i) {
                    case 0: // left
                        // current place: can go to left
                        if (map[myRow][myColumn] == 1 || map[myRow][myColumn] == 3 || map[myRow][myColumn] == 6 || map[myRow][myColumn] == 7) {
                            // next place: can arrived from right
                            if (map[newRow][newColumn] == 1 || map[newRow][newColumn] == 3 || map[newRow][newColumn] == 4 || map[newRow][newColumn] == 5) {
                                // enqueue new position
                                if (queueFront == -1)
                                    queueFront = 0;

                                queueRear++;
                                queueR[queueRear] = newRow;
                                queueC[queueRear] = newColumn;
                                queueT[queueRear] = myTime + 1;
                                visited[newRow][newColumn] = 1;
                            }
                        }
                    break;
                    case 1: // right
                        // current place: can go to right
                        if (map[myRow][myColumn] == 1 || map[myRow][myColumn] == 3 || map[myRow][myColumn] == 4 || map[myRow][myColumn] == 5) {
                            // next place: can arrived from left
                            if (map[newRow][newColumn] == 1 || map[newRow][newColumn] == 3 || map[newRow][newColumn] == 6 || map[newRow][newColumn] == 7) {
                                // enqueue new position
                                if (queueFront == -1)
                                    queueFront = 0;

                                queueRear++;
                                queueR[queueRear] = newRow;
                                queueC[queueRear] = newColumn;
                                queueT[queueRear] = myTime + 1;
                                visited[newRow][newColumn] = 1;
                            }
                        }
                    break;
                    case 2: // up
                        // current place: can go to up
                        if (map[myRow][myColumn] == 1 || map[myRow][myColumn] == 2 || map[myRow][myColumn] == 4 || map[myRow][myColumn] == 7) {
                            // next place: can arrived from down
                            if (map[newRow][newColumn] == 1 || map[newRow][newColumn] == 2 || map[newRow][newColumn] == 5 || map[newRow][newColumn] == 6) {
                                // enqueue new position
                                if (queueFront == -1)
                                    queueFront = 0;

                                queueRear++;
                                queueR[queueRear] = newRow;
                                queueC[queueRear] = newColumn;
                                queueT[queueRear] = myTime + 1;
                                visited[newRow][newColumn] = 1;
                            }
                        }
                    break;
                    case 3: // down
                        // current place: can go to down
                        if (map[myRow][myColumn] == 1 || map[myRow][myColumn] == 2 || map[myRow][myColumn] == 5 || map[myRow][myColumn] == 6) {
                            // next place: can arrived from up
                            if (map[newRow][newColumn] == 1 || map[newRow][newColumn] == 2 || map[newRow][newColumn] == 4 || map[newRow][newColumn] == 7) {
                                // enqueue new position
                                if (queueFront == -1)
                                    queueFront = 0;

                                queueRear++;
                                queueR[queueRear] = newRow;
                                queueC[queueRear] = newColumn;
                                queueT[queueRear] = myTime + 1;
                                visited[newRow][newColumn] = 1;
                            }
                        }
                    break;
                }
            }
        }

        cout << '#' << test_case << ' ' << numArrived << '\n';
    }
}

(C++) 1949. [모의 SW 역량테스트] 등산로 조성

Standard

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

이미 푼 문제임에도 불구하고 처음에 아무 것도 안 떠올라서 당황했지만…
다 짜고 보니 더 효율적인 코드가 됨.
– 최대 높이인 곳들을 list에 삽입
– DFS로 짬. 각 함수에서 visited map을 만들고 처음 최대 높이인 곳을 visited로 처리. (이후 DFS 함수에서는 방문할 수 있는 경우만 실행되니 visited는 항상 1로 처리)
이후, 왼쪽 옆으로 지나갈 수 있는지 (공사 안하고 높이가 낮거나, 공사 안 했으면 공사 후 높이가 낮거나) 확인해서 가능하면 다음 단계로 넘어감.
이후, 오른쪽 옆으로 지나갈 수 있는지 (공사 안하고 높이가 낮거나, 공사 안 했으면 공사 후 높이가 낮거나) 확인해서 가능하면 다음 단계로 넘어감.
이후, 위쪽 옆으로 지나갈 수 있는지 (공사 안하고 높이가 낮거나, 공사 안 했으면 공사 후 높이가 낮거나) 확인해서 가능하면 다음 단계로 넘어감.
이후, 아래쪽 옆으로 지나갈 수 있는지 (공사 안하고 높이가 낮거나, 공사 안 했으면 공사 후 높이가 낮거나) 확인해서 가능하면 다음 단계로 넘어감.
(각 경우, 더 이상 진행이 안 되면 이후 진행이 불가능하므로, 현재까지의 거리를 업데이트함)

#include <iostream>
#include <cstdlib>

using namespace std;

void process (int row, int column, int **map, int size, int k);
void process_(int length, int row, int column, int** map, int** visited, int size, int k, bool constructed);

int maxLength = 1;

int main(int argc, char** argv)
{
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    
    //freopen("input.txt", "r", stdin);
    int T = 0;
    cin >> T;

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

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

        maxLength = 0;

        int numN = 0, numK = 0;
        cin >> numN >> numK; // N: map size, k: construction depth limit

        int maxValue = 0, maxRow[5] = {0}, maxColumn[5] = {0}, maxIdx = -1;

        for (int r = 0; r < numN; r++) {
            for (int c = 0; c < numN; c++) {
                cin >> map[r];
                if (maxValue < map[r]) {
                    maxValue = map[r];
                    maxIdx = 0;
                    maxRow[maxIdx] = r;
                    maxColumn[maxIdx] = c;
                }
                else if (maxValue == map[r]) {
                    maxIdx++;
                    maxRow[maxIdx] = r;
                    maxColumn[maxIdx] = c;
                }
            }
        }

        for (int i = 0; i < maxIdx + 1; i++) {
            process(maxRow[i], maxColumn[i], map, numN, numK);
        }

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

void process (int row, int column, int **map, int size, int k) {
    // visited map
    int **visited = (int**) malloc (size * sizeof(int*));
    for (int i = 0; i < size; i++) 
        visited[i] = (int*) malloc (size * sizeof(int));
    
    for (int i = 0; i < size; i++) 
        for (int j = 0; j < size; j++) 
            visited[i][j] = 0;

    visited[row][column] = 1;        

    bool constructed = false;

    // left direction
    if (column > 0 &amp;&amp; map[row][column] > map[row][column - 1]) 
        process_(2, row, column - 1, map, visited, size, k, constructed);
    else if (constructed == false &amp;&amp; column > 0 &amp;&amp; map[row][column] > map[row][column - 1] - k) {
        int backup = map[row][column - 1];
        map[row][column - 1] = map[row][column] - 1; // k is at least 1, and highest available value makes better
        process_(2, row, column - 1, map, visited, size, k, true);
        map[row][column - 1] = backup;
    }

    // right direction
    if (column < size - 1 &amp;&amp; map[row][column] > map[row][column + 1])
        process_(2, row, column + 1, map, visited, size, k, constructed);
    else if (constructed == false &amp;&amp; column < size - 1 &amp;&amp; map[row][column] > map[row][column + 1] - k) {
        int backup = map[row][column + 1];
        map[row][column + 1] = map[row][column] - 1; // k is at least 1, and highest available value makes better
        process_(2, row, column + 1, map, visited, size, k, true);
        map[row][column + 1] = backup;
    }

    // up direction
    if (row > 0 &amp;&amp; map[row][column] > map[row - 1][column])
        process_(2, row - 1, column, map, visited, size, k, constructed);
    else if (constructed == false &amp;&amp; row > 0 &amp;&amp; map[row][column] > map[row - 1][column] - k) {
        int backup = map[row - 1][column];
        map[row - 1][column] = map[row][column] - 1; // k is at least 1, and highest available value makes better
        process_(2, row - 1, column, map, visited, size, k, true);
        map[row - 1][column] = backup;
    }

    // down direction
    if (row < size - 1 &amp;&amp; map[row][column] > map[row + 1][column])
        process_(2, row + 1, column, map, visited, size, k, constructed);
    else if (constructed == false &amp;&amp; row < size - 1 &amp;&amp; map[row][column] > map[row + 1][column] - k) {
        int backup = map[row + 1][column];
        map[row + 1][column] = map[row][column] - 1; // k is at least 1, and highest available value makes better
        process_(2, row + 1, column, map, visited, size, k, true);
        map[row + 1][column] = backup;
    }
}

void process_(int length, int row, int column, int** map, int** visited, int size, int k, bool constructed) {
    int **newVisited = (int**) malloc (size * sizeof(int*));
    for (int i = 0; i < size; i++) 
        newVisited[i] = (int*) malloc (size * sizeof(int));
    
    for (int i = 0; i < size; i++) 
        for (int j = 0; j < size; j++) 
            newVisited[i][j] = visited[i][j];

    newVisited[row][column] = 1;
    
    if (column > 0 &amp;&amp; newVisited[row][column - 1] == 0 &amp;&amp; map[row][column] > map[row][column - 1])
        process_(length + 1, row, column - 1, map, newVisited, size, k, constructed);
    else if (constructed == false &amp;&amp; column > 0 &amp;&amp; newVisited[row][column - 1] == 0 &amp;&amp; map[row][column] > map[row][column - 1] - k) {
        int backup = map[row][column - 1];
        map[row][column - 1] = map[row][column] - 1; // k is at least 1, and highest available value makes better
        process_(length + 1, row, column - 1, map, newVisited, size, k, true);
        map[row][column - 1] = backup;
    }
    else { // can't go further
        if (maxLength < length)
            maxLength = length;
    }

    if (column < size - 1 &amp;&amp; newVisited[row][column + 1] == 0 &amp;&amp; map[row][column] > map[row][column + 1])
        process_(length + 1, row, column + 1, map, newVisited, size, k, constructed);
    else if (constructed == false &amp;&amp; column < size - 1 &amp;&amp; newVisited[row][column + 1] == 0 &amp;&amp; map[row][column] > map[row][column + 1] - k) {
        int backup = map[row][column + 1];
        map[row][column + 1] = map[row][column] - 1; // k is at least 1, and highest available value makes better
        process_(length + 1, row, column + 1, map, newVisited, size, k, true);
        map[row][column + 1] = backup;
    }
    else { // can't go further
        if (maxLength < length)
            maxLength = length;
    }

    if (row > 0 &amp;&amp; newVisited[row - 1][column] == 0 &amp;&amp; map[row][column] > map[row - 1][column])
        process_(length + 1, row - 1, column, map, newVisited, size, k, constructed);
    else if (constructed == false &amp;&amp; row > 0 &amp;&amp; newVisited[row - 1][column] == 0 &amp;&amp; map[row][column] > map[row - 1][column] - k) {
        int backup = map[row - 1][column];
        map[row - 1][column] = map[row][column] - 1; // k is at least 1, and highest available value makes better
        process_(length + 1, row - 1, column, map, newVisited, size, k, true);
        map[row - 1][column] = backup;
    }
    else { // can't go further
        if (maxLength < length)
            maxLength = length;
    }

    if (row < size - 1 &amp;&amp; newVisited[row + 1][column] == 0 &amp;&amp; map[row][column] > map[row + 1][column])
        process_(length + 1, row + 1, column, map, newVisited, size, k, constructed);
    else if (constructed == false &amp;&amp; row < size - 1 &amp;&amp; newVisited[row + 1][column] == 0 &amp;&amp; map[row][column] > map[row + 1][column] - k) {
        int backup = map[row + 1][column];
        map[row + 1][column] = map[row][column] - 1; // k is at least 1, and highest available value makes better
        process_(length + 1, row + 1, column, map, newVisited, size, k, true);
        map[row + 1][column] = backup;
    }
    else { // can't go further
        if (maxLength < length)
            maxLength = length;
    }
}

(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 &amp;&amp; r != numN -1 &amp;&amp; c != 0 &amp;&amp; c != numN - 1 &amp;&amp; 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;
        }
    }
}