Gidhub BE Developer

[SW Expert Academy] 2382. 미생물 격리

2018-08-31
goodGid

Problem

Problem URL : 미생물 격리


[1] Answer Code (18. 08. 31)

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

struct Bug {
    int x;
    int y;
    int cnt;
    int dir;
    Bug(int x,int y,int cnt, int dir):x(x),y(y),cnt(cnt),dir(dir){}
};

int map[101][101];
int change_dir[] = {0,2,1,4,3};
pair<int,int> max_bug[101][101];

int main(){
    int TC;
    cin >> TC;
    for (int tc=1; tc<=TC; tc++) {
        int n,m,k; // 셀의 개수 N, 격리 시간 M, 미생물 군집의 개수 K
        cin >> n >> m >>k ;
        memset(max_bug,0,sizeof(max_bug));
        vector<Bug> bug;
        for(int i=0; i<k; i++){
            int a,b,c,d;
            cin >> a >> b >> c >> d;
            bug.push_back(Bug(a,b,c,d));
        }
        
        while (m--) {
            memset(map,-1,sizeof(map));
            // Bug Move
            for(int i=0; i<k; i++){
                if(bug[i].cnt == 0) continue;
                
                if(bug[i].dir == 1) bug[i].x -= 1;
                else if(bug[i].dir == 2) bug[i].x += 1;
                else if(bug[i].dir == 3) bug[i].y -= 1;
                else if(bug[i].dir == 4) bug[i].y += 1;
                
                // 가장 자리일 경우
                if( bug[i].x == 0 || bug[i].x == n-1 || bug[i].y == 0 || bug[i].y == n-1){
                    bug[i].cnt /= 2;
                    bug[i].dir = change_dir[bug[i].dir];
                    map[ bug[i].x ][ bug[i].y ] = i;
                }
                // 이동한 장소에 이미 있을 시
                else if(map[ bug[i].x ][ bug[i].y ] != -1){
                    // 해당 좌표에 존재하는 Bug의 Index
                    int pre_bug_idx = map[ bug[i].x ][ bug[i].y ];
                    if( max_bug[ bug[i].x ][ bug[i].y ].first > bug[i].cnt){
                        bug[pre_bug_idx].cnt += bug[i].cnt;
                        bug[i].cnt = 0;
                    }
                    else{
                        max_bug[ bug[i].x ][ bug[i].y ] = {bug[i].cnt, bug[i].dir}; // [1]
                        bug[i].cnt += bug[pre_bug_idx].cnt;
                        bug[pre_bug_idx].cnt = 0;
                        map[ bug[i].x ][ bug[i].y ] = i; // map에 새로운 bug index로 초기화
                        // max_bug[ bug[i].x ][ bug[i].y ] = {bug[i].cnt, bug[i].dir}; // [2]
                    }
                } // end of else if
                else{
                    map[ bug[i].x ][ bug[i].y ]= i;
                    max_bug[ bug[i].x ][ bug[i].y ] = {bug[i].cnt, bug[i].dir};
                }
            } // end of for i
        } // end of while
        
        int ans = 0;
        for(int i=0; i<k; i++){
            ans += bug[i].cnt;
        }
        printf("#%d %d\n",tc, ans);
    } // end of for tc
    return 0;
}

Reivew

  • 으아아아아아 [2]에 두고 하니까 자꾸 틀렸다. [1]으로 옮기니까 맞네
    너무 오래 걸렸다. 반성해야겠다.

[2] Wrong Code (18. 08. 31)

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

struct Bug {
    int x;
    int y;
    int cnt;
    int dir;
    Bug(int x,int y,int cnt, int dir):x(x),y(y),cnt(cnt),dir(dir){}
};

int map[100][100];
int change_dir[] = {0,2,1,4,3};

int main(){
    int TC;
    cin >> TC;
    for (int tc=1; tc<=TC; tc++) {
        int n,m,k; // 셀의 개수 N, 격리 시간 M, 미생물 군집의 개수 K
        cin >> n >> m >>k ;
        
        vector<Bug> bug;
        for(int i=0; i<k; i++){
            int a,b,c,d;
            cin >> a >> b >> c >> d;
            bug.push_back(Bug(a,b,c,d));
        }
        
        while (m--) {
            memset(map,-1,sizeof(map));
            // Bug Move
            for(int i=0; i<k; i++){
                if(bug[i].cnt == 0) continue;
                
                if(bug[i].dir == 1) bug[i].x -= 1;
                else if(bug[i].dir == 2) bug[i].x += 1;
                else if(bug[i].dir == 3) bug[i].y -= 1;
                else if(bug[i].dir == 4) bug[i].y += 1;
                
                // 가장 자리일 경우
                if( bug[i].x == 0 || bug[i].x == n-1 || bug[i].y == 0 || bug[i].y == n-1){
                    bug[i].cnt /= 2;
                    bug[i].dir = change_dir[bug[i].dir];
                    map[ bug[i].x ][ bug[i].y ] = i;
                }
                // 이동한 장소에 이미 있을 시
                else if(map[ bug[i].x ][ bug[i].y ] != -1){
                    // 해당 좌표에 존재하는 Bug의 Index
                    int pre_bug_idx = map[ bug[i].x ][ bug[i].y ];
                    if( bug[pre_bug_idx].cnt > bug[i].cnt){
                        bug[pre_bug_idx].cnt += bug[i].cnt;
                        bug[i].cnt = 0;
//                        cout << pre_bug_idx << " take " << i << endl;
                    }
                    else{
                        bug[i].cnt += bug[pre_bug_idx].cnt;
                        bug[pre_bug_idx].cnt = 0;
                        // map에 새로운 bug index로 초기화
                        map[ bug[i].x ][ bug[i].y ] = i;
//                        cout << i << " take " << pre_bug_idx << endl;
                    }
                } // end of else if
                else{
                    map[ bug[i].x ][ bug[i].y ]= i;
                }
            } // end of for i
        } // end of while
        
        int ans = 0;
        for(int i=0; i<k; i++){
            ans += bug[i].cnt;
        }
        printf("#%d %d\n",tc, ans);
    } // end of for tc
    return 0;
}

Review

  • 로직구현은 30분안에 해서 코딩까지 빠른 시간내에 했는데 틀렸다.

  • 처음엔 memset(map,-1,sizeof(map)); 이 부분을 놓쳤다
    그리고 도저히 모르겠어서 질문을 남겼는데 굉장히 단순한 실수였다. 그게 내 실력이지만… ㅠㅠ

  • 다음처럼 입력이 주어질 때 1,2번째 미생물이 합쳐지면서 원래는 3번째 미생울 집단의 3(좌)방향으로 가야하는데
    1,2번째 미생물이 먼저 합쳐지고 미생물 수도 많기 때문에 4(우)방향으로 진행이 된다.

1
7 3 3
1 1 120 4
2 2 100 1
1 3 150 3
  • 위 문제를 수정한 코드를 제출했는데 4개가 틀린다. 그래서 다시 질문을 했다.

[3] Answer Code (18. 06. 01)


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

p map[2][100][100];
p max_node[100][100];
int n,m,k;
int ans;
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};
int edgeDir[] = {2,1,4,3};

p changeDir(int x, int y,int dir){
    if(dir == 1)
        return p(x+dx[3], y+dy[3]);
    else if(dir == 2)
        return p(x+dx[1], y+dy[1]);
    else if(dir == 3)
        return p(x+dx[2], y+dy[2]);
    else
        return p(x+dx[0], y+dy[0]);
}

int main(){
    int T;
    cin >> T;
    
    for(int i=1; i<=T; i++){
        memset(map,0,sizeof(map));
        memset(max_node,0,sizeof(max_node));
        cin >> n >> m >> k;
        ans = 0;
        
        for(int j=0; j<k; j++){
            int x,y,cnt,dir;
            scanf("%d%d%d%d",&x,&y,&cnt,&dir);
            map[0][x][y] = make_pair(cnt, dir);
        }
        bool flag = true;
        while(m--){
            for(int i=0; i<n; i++){
                for(int j=0; j<n; j++){
                    if(map[!flag][i][j].first != 0){ // 미생물이 있다.
                        int cnt = map[!flag][i][j].first;
                        int dir = map[!flag][i][j].second;
                        p _dir = changeDir(i,j, dir);
                        int nx = _dir.first;
                        int ny = _dir.second;
                        
                        // 가장자리
                        if( nx == 0 || nx == n-1 || ny == 0 || ny == n-1){
                            map[flag][nx][ny] = p( cnt >> 1, edgeDir[dir-1]);
                        }
                        // 중복될 경우
                        else if(map[flag][nx][ny].first != 0){
                            if( max_node[nx][ny].first < map[!flag][i][j].first){
                                max_node[nx][ny].first = map[!flag][i][j].first; // [1]
                                max_node[nx][ny].second = map[!flag][i][j].second;
                            }
                            map[flag][nx][ny].first += map[!flag][i][j].first;
                            map[flag][nx][ny].second = max_node[nx][ny].second;
                        }
                        else{ // 중복 X
                            max_node[nx][ny] = map[flag][nx][ny] = p(cnt,dir);
                        }
                        map[!flag][i][j] = p(0,0);
                    }
                }
            } // End of For i
            flag = !flag;
        } // End of While
        
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(map[!flag][i][j].first != 0)
                    ans += map[!flag][i][j].first;
            }
        }
        printf("#%d %d\n",i,ans);
    }
    
    return 0;
}


Reivew

  • SW Expert Academy 문제.

  • [1] Code 때문에 틀렸었다.

  • 확실히 처음풀었을 때 보다 코드는 간결해졌다.


[4] Answer Code (18. 04. 01)


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

struct Node{    // [1]
    int x;
    int y;
    int num;
    int dir;
};

int dx[] = {0,-1,1,0,0};
int dy[] = {0,0,0,-1,1};
vector<int> map[100][100];  // [2]

int main(){
    int tc;
    cin >> tc;
    
    for(int i=1; i<=tc; i++){
        int n,m,k;
        cin >> n >> m >> k;
        
        vector<Node> v(k);  // [3]
        for(int i=0; i<k; i++){
            cin >> v[i].x >> v[i].y >> v[i].num >> v[i].dir;    // [4]
            map[v[i].x][v[i].y].push_back(i);
        }
        
        while (m--) {
            for(int i=0; i<k; i++){
                if( v[i].num == 0) continue;
                map[v[i].x][v[i].y].clear();
            }
            
            for(int i=0; i<k; i++){
                if( v[i].num == 0) continue;
                v[i].x += dx[ v[i].dir ];
                v[i].y += dy[ v[i].dir ];
                map[v[i].x][v[i].y].push_back(i);
            }
            
            // Check Condition
            // 1. Check whether it is located at the edge
            // 2. Check for duplicates
            for(int i=0; i<k; i++){
                if( v[i].num == 0) continue;
                
                if( v[i].x == 0 || v[i].x == n-1 || v[i].y == 0 || v[i].y == n-1){ // [5]
                    v[i].num /= 2;
                    
                    if( v[i].dir == 1 ) v[i].dir = 2;
                    else if( v[i].dir == 2) v[i].dir = 1;
                    else if( v[i].dir == 3) v[i].dir = 4;
                    else if( v[i].dir == 4) v[i].dir = 3;
                }
                else if( map[v[i].x][v[i].y].size() > 1 ){
                    int max_idx = 0;
                    int max_num = 0;
                    int max_dir = 0;
                    int sum = 0;
                    
                    int size = (int)map[v[i].x][v[i].y].size();
                    for(int j=0; j<size; j++){
                        sum += v[map[v[i].x][v[i].y][j]].num;
                        
                        if( v[map[v[i].x][v[i].y][j]].num > max_num ){
                            max_idx = map[v[i].x][v[i].y][j];
                            max_dir = v[map[v[i].x][v[i].y][j]].dir;
                            max_num = v[map[v[i].x][v[i].y][j]].num;
                        }
                        v[map[v[i].x][v[i].y][j]].num = 0;
                    }
                    
                    v[max_idx].num = sum;
                    v[max_idx].dir = max_dir;
                } // End of else if
            } // End of for Loop
        } // End of While Loop
        
            int ans = 0;
            for(int i=0; i<k; i++){
                ans += v[i].num;
                map[v[i].x][v[i].y].clear();
            }
        printf("#%d %d\n",i,ans);
    } // End of For Loop
    
    return 0;
}

Review

  • SW Expert Academy 문제.

  • [1], [2], [3], [4] 이런 디테일한 코딩 스킬이 Samsung 코딩 테스트를 위해서 필요한거 같다.

  • 많은 시간이 걸렸지만 그 만큼 재밌었고 많이 배웠다.

  • 코드가 길어지다보니 { }구조 파악하는데 시간이 걸렸다.
    주석으로 매칭되는 짝을 명시하자

  • [5] : v[i].x == n으로 해서 틀렸다. n인지 n-1인지 조심하자!


Comments

Content