Gidhub BE Developer

[SW Expert Academy] 1953. 탈주범 검거

2018-05-07
goodGid

Problem

Problem URL : 탈주범 검거


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

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

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

int map[50][50];
int v[50][50]; // v is visit
int row,col;

struct Node{
    int x;
    int y;
    int time;
    Node(int a, int b, int c): x(a), y(b), time(c) {};
};

bool inRange(int x, int y){
    if( x < 0 || x >= row || y < 0 || y >= col)
        return false;
    return true;
}

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,0,sizeof(map));
        memset(v, 0, sizeof(v));
        int st_x;
        int st_y;
        int L;
        cin >> row >> col >> st_x >> st_y >> L ;
        
        for(int i=0; i<row; i++) for(int j=0; j<col; j++) cin >> map[i][j];
        
        queue<Node> q;
        q.push(Node(st_x,st_y,1));
        
        int cnt = 1;
        while (! q.empty()) {
            int x = q.front().x;
            int y = q.front().y;
            int time = q.front().time;
            q.pop();
            
            if(time == L)
                break;
            v[x][y] = 1;
            
            for(int i=0; i<4; i++){
                int nx = x + dx[i];
                int ny = y + dy[i];

                // 범위 밖인 경우
                if(! inRange(nx, ny))
                    continue;
                int now_value = map[x][y];
                
                if( now_value == 1 && ! v[nx][ny]){
                    int next_value = map[nx][ny];
                    if( i == 0 ){ // Right
                        if( next_value == 1 || next_value == 3
                           || next_value == 6 || next_value == 7){
                            cnt++;
                            v[nx][ny] = 1;
                            q.push(Node(nx,ny,time+1));
                        }
                    }
                    else if( i == 1){ // Bottom
                        if( next_value == 1 || next_value == 2
                           || next_value == 4 || next_value == 7){
                            cnt++;
                            v[nx][ny] = 1;
                            q.push(Node(nx,ny,time+1));
                        }
                    }
                    else if( i == 2){ // Left
                        if( next_value == 1 || next_value == 3
                           || next_value == 4 || next_value == 5){
                            cnt++;
                            v[nx][ny] = 1;
                            q.push(Node(nx,ny,time+1));
                        }
                    }
                    else if( i == 3){ // Top
                        if( next_value == 1 || next_value == 2
                           || next_value == 5 || next_value == 6){
                            cnt++;
                            v[nx][ny] = 1;
                            q.push(Node(nx,ny,time+1));
                        }
                    }
                } // end of now_value = 1

                else if( now_value == 2 && ! v[nx][ny]){
                    int next_value = map[nx][ny];
                    if( i == 0 ){ // Right
                    }
                    else if( i == 1){ // Bottom
                        if( next_value == 1 || next_value == 2
                           || next_value == 4 || next_value == 7){
                            cnt++;
                            v[nx][ny] = 1;
                            q.push(Node(nx,ny,time+1));
                        }
                    }
                    else if( i == 2){ // Left
                    }
                    else if( i == 3){ // Top
                        if( next_value == 1 || next_value == 2
                           || next_value == 5 || next_value == 6){
                            cnt++;
                            v[nx][ny] = 1;
                            q.push(Node(nx,ny,time+1));
                        }
                    }
                } // end of now_value = 2
                
                else if( now_value == 3 && ! v[nx][ny]){
                    int next_value = map[nx][ny];
                    if( i == 0 ){ // Right
                        if( next_value == 1 || next_value == 3
                           || next_value == 6 || next_value == 7){
                            cnt++;
                            v[nx][ny] = 1;
                            q.push(Node(nx,ny,time+1));
                        }
                    }
                    else if( i == 1){ // Bottom
                    }
                    else if( i == 2){ // Left
                        if( next_value == 1 || next_value == 3
                           || next_value == 4 || next_value == 5){
                            cnt++;
                            v[nx][ny] = 1;
                            q.push(Node(nx,ny,time+1));
                        }
                    }
                    else if( i == 3){ // Top
                    }
                } // end of now_value = 3
                
                else if( now_value == 4 && ! v[nx][ny]){
                    int next_value = map[nx][ny];
                    if( i == 0 ){ // Right
                        if( next_value == 1 || next_value == 3
                           || next_value == 6 || next_value == 7){
                            cnt++;
                            v[nx][ny] = 1;
                            q.push(Node(nx,ny,time+1));
                        }
                    }
                    else if( i == 1){ // Bottom
                    }
                    else if( i == 2){ // Left
                    }
                    else if( i == 3){ // Top
                        if( next_value == 1 || next_value == 2
                           || next_value == 5 || next_value == 6){
                            cnt++;
                            v[nx][ny] = 1;
                            q.push(Node(nx,ny,time+1));
                        }
                    }
                } // end of now_value = 4
                
                else if( now_value == 5 && ! v[nx][ny]){
                    int next_value = map[nx][ny];
                    if( i == 0 ){ // Right
                        if( next_value == 1 || next_value == 3
                           || next_value == 6 || next_value == 7){
                            cnt++;
                            v[nx][ny] = 1;
                            q.push(Node(nx,ny,time+1));
                        }
                    }
                    else if( i == 1){ // Bottom
                        if( next_value == 1 || next_value == 2
                           || next_value == 4 || next_value == 7){
                            cnt++;
                            v[nx][ny] = 1;
                            q.push(Node(nx,ny,time+1));
                        }
                    }
                    else if( i == 2){ // Left
                    }
                    else if( i == 3){ // Top
                    }
                } // end of now_value = 5
                
                else if( now_value == 6 && ! v[nx][ny]){
                    int next_value = map[nx][ny];
                    if( i == 0 ){ // Right
                    }
                    else if( i == 1){ // Bottom
                        if( next_value == 1 || next_value == 2
                           || next_value == 4 || next_value == 7){
                            cnt++;
                            v[nx][ny] = 1;
                            q.push(Node(nx,ny,time+1));
                        }
                    }
                    else if( i == 2){ // Left
                        if( next_value == 1 || next_value == 3
                           || next_value == 4 || next_value == 5){
                            cnt++;
                            v[nx][ny] = 1;
                            q.push(Node(nx,ny,time+1));
                        }
                    }
                    else if( i == 3){ // Top
                    }
                } // end of now_value = 6
                
                else if( now_value == 7 && ! v[nx][ny]){
                    int next_value = map[nx][ny];
                    if( i == 0 ){ // Right
                    }
                    else if( i == 1){ // Bottom
                    }
                    else if( i == 2){ // Left
                        if( next_value == 1 || next_value == 3
                           || next_value == 4 || next_value == 5){
                            cnt++;
                            v[nx][ny] = 1;
                            q.push(Node(nx,ny,time+1));
                        }
                    }
                    else if( i == 3){ // Top
                        if( next_value == 1 || next_value == 2
                           || next_value == 5 || next_value == 6){
                            cnt++;
                            v[nx][ny] = 1;
                            q.push(Node(nx,ny,time+1));
                        }
                    }
                } // end of now_value = 7
            } // end of for i
        }
        cout << "#" << tc << " " << cnt << endl ;
    }
    return 0;
}

Review

  • 1번 모양(+)일 때 좌우 조건을 빼먹어서 시간이 걸렸다.

  • 1번 조건이 아니였다면 50분 컷이였는데 아쉽다.

  • 1번 모양
    • 상 : 1 2 5 6
    • 하 : 1 2 4 7
    • 좌 : 1 3 4 5
    • 우 : 1 3 6 7
  • 2번 모양
    • 상 : 1 2 5 6
    • 하 : 1 2 4 7
  • 3번 모양
    • 좌 : 1 3 4 5
    • 우 : 1 3 6 7
  • 4번 모양
    • 상 : 1 2 5 6
    • 우 : 1 3 6 7
  • 5번 모양
    • 하 : 1 2 4 7
    • 우 : 1 3 6 7
  • 6번 모양
    • 하 : 1 2 4 7
    • 좌 : 1 3 4 5
  • 7번 모양
    • 상 : 1 2 5 6
    • 우 : 1 3 6 7

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


#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
#define P pair<int,int>
using namespace std;
vector<int> v[7];
int map[50][50];
int visit[50][50];
int dx[] = {0,1,1,1,0,-1,-1,-1};
int dy[] = {1,1,0,-1,-1,-1,0,1};

bool chkShape(int dir, int value){
    if(dir == 0 || dir == 7){
        if(value == 1 || value == 3 || value == 6 || value == 7){
            return true;
        } else
            return false;
    }
    else if(dir == 1 || dir == 2 || dir == 3){
        if(value == 1 || value == 2 || value == 4 || value == 7){
            return true;
        } else
            return false;
    }
    else if(dir == 4 || dir == 5){
        if(value == 1 || value == 3 || value == 4 || value == 5){
            return true;
        } else
            return false;
    }
    else { // 6
        if(value == 1 || value == 2 || value == 5 || value == 6){
            return true;
        } else
            return false;
    }
}

vector<int> getDirection(int dir){
    vector<int> v;
    if(dir == 1){
        v.push_back(0); v.push_back(2); v.push_back(4); v.push_back(6);
    }
    else if( dir == 2){
        v.push_back(2); v.push_back(6);
    }
    else if( dir == 3){
        v.push_back(0); v.push_back(4);
    }
    else if( dir == 4){
        v.push_back(0); v.push_back(6);
    }
    else if( dir == 5 ){
        v.push_back(0); v.push_back(2);
    }
    else if( dir == 6){
        v.push_back(2); v.push_back(4);
    }
    else if( dir == 7){
        v.push_back(4); v.push_back(6);
    }
    return v;
}

int main(){
    int tc;
    cin >> tc;
    
    for(int st=1; st<=tc; st++){
        memset(map,0,sizeof(map));
        memset(visit,0,sizeof(visit));
        
        vector<int> v;
        queue<P> q;
        
        int n,m,X,Y,time;
        cin >> n >> m >> X >> Y >> time;
        
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                scanf("%d",&map[i][j]);
            }
        }
        
        q.push({X,Y});
        visit[X][Y] = 1;
        int cnt = 0;
        for(int i=0; i<time; i++){
            int size = (int)q.size();
            
            for(int k=0; k<size; k++){
                int x = q.front().first;
                int y = q.front().second;
                q.pop();
                cnt ++ ;
                
                vector<int> _v= getDirection(map[x][y]);
                int _v_size = (int)_v.size();
                for(int c=0; c<_v_size; c++){
                    int nx = x + dx[_v[c]];
                    int ny = y + dy[_v[c]];
                    if( nx < 0 || nx > n-1 || ny < 0 || ny > m-1) continue;
                    if(! visit[nx][ny] && chkShape(_v[c],map[nx][ny])){
                        visit[nx][ny] = 1;
                        q.push({nx,ny});
                    }
                } // End of y for Loop
            } // End of k for Loop
        } // End of i for Loop
        printf("#%d %d\n",st,cnt);
    }
    
    return 0;
}

Review

  • SW Expert Academy 문제.

  • 파이프 모양에 따른 호환성 체크 조건을 빼먹고 코딩을 시작했다.

  • 모양에 따른 호환성 체크를 어떻게 해주면 좋을까?

  • 2시간 30분 걸림

  • chkShape()를 만드는데 굉장히 오랜 시간이 걸렸다.

  • getDirection()를 만드는데 오랜 시간이 걸리지 않았지만 실수를 했다.



Comments

Content