Gidhub BE Developer

[SW Expert Academy] 1767. 프로세서 연결하기

2018-05-07
goodGid

Problem

Problem URL : 프로세서 연결하기


[1] Answer Code (18. 10. 10)

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;

int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};

int ans_core;
int ans_line;
int n;

int map[13][13];

struct Node{
    int x;
    int y;
    Node(int _x, int _y): x(_x), y(_y) {};
};
vector<Node> core_v; // vector list of core's


bool isEdge(int x, int y){
    if( (x == 0 || x == n-1) || ( y == 0 || y == n-1 ))
        return true;
    else
        return false;
}

bool isCore(int idx, int dir_idx){
    int x = core_v[idx].x;
    int y = core_v[idx].y;
    
    while (1) {
        if( isEdge(x, y))
            break;
        x += dx[dir_idx];
        y += dy[dir_idx];
        if(map[x][y])
            return true;
    }
    return false;
}

int fillLine(int idx, int dir_idx, int value){
    int x = core_v[idx].x;
    int y = core_v[idx].y;
    int line_cnt = 0;
    while (1) {
        x += dx[dir_idx];
        y += dy[dir_idx];
        if( x < 0 || x >= n || y < 0 || y >= n )
            break;
        map[x][y] = value;
        line_cnt++;
    }
    return line_cnt;
}

void dfs(int idx, int core_cnt, int line_cnt){
    if(idx == core_v.size()){
        if(ans_core < core_cnt){
            ans_core = core_cnt;
            ans_line = line_cnt;
        }
        else if( ans_core == core_cnt){
            ans_line = ans_line < line_cnt ? ans_line : line_cnt;
        }
        return;
    }
    
    if( isEdge(core_v[idx].x, core_v[idx].y) ){
        dfs(idx+1,core_cnt+1,line_cnt);
    }
    else{
        for(int i=0; i<4; i++){ // 4방향 체크
            if(! isCore(idx, i)){
                int add_line = fillLine(idx,i,1);
                dfs(idx+1, core_cnt + 1, line_cnt + add_line);
                fillLine(idx,i,0);
            }
        }
        
        /*
         설치하지 않고 Pass
         00000
         01110
         01110
         01110
         00000
         이런 경우에 가운데 있는 코어는 Pass해야한다.
         */
        dfs(idx+1,core_cnt,line_cnt);
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int TC;
    cin >> TC;
    
    for(int tc=1; tc<=TC; tc++){
        memset(map,-1,sizeof(map));
        core_v.clear();
        
        ans_core = -1;
        ans_line = 2e9;
        cin >> n;
        
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++){
                cin >> map[i][j];
                if(map[i][j] == 1)
                    core_v.push_back(Node(i,j));
            }
        }
        dfs(0,0,0);
        cout << "#" << tc << " " << ans_line << endl;
    }
    return 0;
}

Review

  • 생각보다 오래걸렸다.

[2] Answer Code (18. 05. 08)

#include <iostream>
#include <vector>
#include <cstring>
#define P pair<int,int>
using namespace std;

int n,map[12][12];
int num,cnt,size;
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};

int draw(int x, int y, int dir, bool chk){
    int cnt = 0;
    int _value = chk;
    
    while (1) {
        x += dx[dir];
        y += dy[dir];
        cnt ++;
        map[x][y] = _value;
        if( x == 0 || x == n-1 || y == 0 || y == n-1 )
            break;
    }
    return cnt;
}

void dfs(vector<P> &v, int idx, int _num, int _cnt){
    if( idx >= size ){
        if( num < _num ){ // 많은 Core가 우선
            num = _num;
            cnt = _cnt;
        }
        else if( num == _num && cnt > _cnt) // Core 수는 같고 cnt값이 작을 때
            cnt = _cnt;
    }
    else {
        int x = v[idx].first;
        int y = v[idx].second;
        
        if( x == 0 || x == n-1 || y == 0 || y == n-1) // 가장 자리는 그냥 idx와 처리한 Core수만 증가
            dfs(v,idx+1,_num+1, _cnt);
        else{
            for(int i=0; i<4; i++){
                x = v[idx].first;
                y = v[idx].second;
                while (1) {
                    x += dx[i];
                    y += dy[i];
                    // 중지 조건이
                    // 1. map[x][y] == 1이면 전선을 못 놓는다.
                    // 2. 가장자리까지 왔다.
                    if( map[x][y] == 1 || x == 0 || x == n-1 || y == 0 || y == n-1){
                        break;
                    }
                } // End of While
                
                // 1번 조건으로인해 중간에 끊기면 조건을 위배하므로 false
                if( map[x][y] == 0 && (x == 0 || x == n-1 || y == 0 || y == n-1 )){
                    // Draw
                    int draw_cnt = draw(v[idx].first, v[idx].second, i, true);
                    dfs(v,idx+1, _num+1, _cnt+draw_cnt);
                    // Cancle Draw
                    draw(v[idx].first, v[idx].second, i, false);
                }
                else
                    continue;
            }
        }
        // 0 1 0
        // 1 1 1
        // 0 1 0
        // 위 와 같은 구조일 때 (1,1)은
        // idx값만 넘겨야 하기 때문에
        dfs(v,idx+1,_num,_cnt);
    }
}

int main(){
    int tc;
    cin >> tc;
    
    for(int st=1; st<=tc; st++){
        num = 0;
        cnt = 2e9;
        memset(map, 0, sizeof(map));
        
        cin >> n;
        
        vector<P> v;
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                int tmp;
                scanf("%d",&tmp);
                if(tmp){
                    map[i][j] = tmp;
                    v.push_back({i,j});
                }
            }
        }
        size = (int)v.size();
        dfs(v,0,0,0);
        printf("#%d %d\n",st,cnt);
    }
    return 0;
}

Review

  • 어떻게 접근해야할 지 떠오르지 않아 답을 보았다.

  • 이 문제를 통해서 배운점 4가지
    시간 복잡도 / 문제접근법 / draw 함수에서 T/F로 채우기 / vector 넘기기 /DFS 시간복잡도


[3] Wrong Code (18. 05. 07)

#include <iostream>
#include <vector>
#include <cstring>
#define P pair<int,int>
using namespace std;

int n,map[12][12];
int num,cnt,size;
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};

int draw(int x, int y, int dir, bool chk){
    int cnt = 0;
    int _value = chk;
    
    while (1) {
        x += dx[dir];
        y += dy[dir];
        cnt ++;
        map[x][y] = _value;
        if( x == 0 || x == n-1 || y == 0 || y == n-1 )
            break;
    }
    return cnt;
}

void dfs(vector<P> &v, int idx, int _num, int _cnt){
    if( idx >= size ){
        if( num <= _num ){ // 많은 Core가 우선
            if( cnt > _cnt){ // 그 중 cnt 작은 값
                num = _num;
                cnt = _cnt;
        }
        else if( num == _num && cnt > _cnt) // Core 수는 같고 cnt값이 작을 때
            cnt = _cnt;
        }
    }
    else {
        int x = v[idx].first;
        int y = v[idx].second;
        
        if( x == 0 || x == n-1 || y == 0 || y == n-1) // 가장 자리는 그냥 idx와 처리한 Core수만 증가
            dfs(v,idx+1,_num+1, _cnt);
        else{
            for(int i=0; i<4; i++){
                x = v[idx].first;
                y = v[idx].second;
                while (1) {
                    x += dx[i];
                    y += dy[i];
                    // 중지 조건이
                    // 1. map[x][y] == 1이면 전선을 못 놓는다.
                    // 2. 가장자리까지 왔다.
                    if( map[x][y] == 1 || x == 0 || x == n-1 || y == 0 || y == n-1){
                        break;
                    }
                } // End of While
                
                // 1번 조건으로인해 중간에 끊기면 조건을 위배하므로 false
                if( map[x][y] == 0 && (x == 0 || x == n-1 || y == 0 || y == n-1 )){
                    // Draw
                    int draw_cnt = draw(v[idx].first, v[idx].second, i, true);
                    dfs(v,idx+1, _num+1, _cnt+draw_cnt);
                    // Cancle Draw
                    draw(v[idx].first, v[idx].second, i, false);
                }
                else
                    continue;
            }
        }
        // 0 1 0
        // 1 1 1
        // 0 1 0
        // 위 와 같은 구조일 때 (1,1)은
        // idx값만 넘겨야 하기 때문에
        dfs(v,idx+1,_num,_cnt);
    }
}

int main(){
    int tc;
    cin >> tc;
    
    for(int st=1; st<=tc; st++){
        num = 0;
        cnt = 2e9;
        memset(map, 0, sizeof(map));
        
        cin >> n;
        
        vector<P> v;
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                int tmp;
                scanf("%d",&tmp);
                if(tmp){
                    map[i][j] = tmp;
                    v.push_back({i,j});
                }
            }
        }
        size = (int)v.size();
        dfs(v,0,0,0);
        printf("#%d %d\n",st,cnt);
    }
    return 0;
}

Review

  • 50개 중 41개가 맞는다.

  • 어디가 틀린걸까? 모르겠어서 SWEA 사이트에 질문을 올렸다.

  • 이유를 찾았다.
    [ if( cnt > _cnt){ // 그 중 cnt 작은 값 ]
    이 부분이 잘못되었다. num값이 크면 우선순위가 높기 때문에 무조건 초기화를 해줘야한다.


Comments

Content