Gidhub BE Developer

[BOJ] 15684. 사다리 조작

2018-10-03
goodGid
Algorithm

Problem

Problem URL : 사다리 조작

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

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

int ans;
int row,col,h;

int map[275][15];
int target_line;

bool chk(){
    for(int i=1; i<=col; i++){
        int origin_c_idx = i;
        int r_idx = 1;
        int c_idx = i;
        
        while (1) {
            if(map[r_idx][c_idx] == 1) // 오른쪽으로 라인이 있는 경우
                c_idx ++;
            else if(map[r_idx][c_idx - 1] == 1) // 왼쪽으로 라인이 있는 경우
                c_idx --;
            r_idx ++; // 1 time 지나면 무조건 한 칸 아래로 이동
            
            if(r_idx == row + 1)
                break;
        } // end of while
        if(origin_c_idx != c_idx)
            return false;
    } // end of for i
    return true;
}

void dfs(int r_idx, int c_idx, int use_line_cnt){
    if( use_line_cnt == target_line ){
        if(chk()){
            ans = target_line;
        }
        return ;
    }
    
    for(int r=r_idx; r<=row; r++){
        /*
        나는 1,1이라고 입력이 주어진다면
        무조건 오른쪽으로만 Line을 놓는다 생각했다.
        
        그렇기 때문에 c는 col까지가 아닌 col-1까지만 돌린다.
        col이 5개라면
        5번째 col은 오른쪽으로 놓는 경우는 없기 때문이다.
        */
        for(int c=c_idx; c<col; c++){ 
            if(map[r][c] != 1 && map[r][c-1] != 1 && map[r][c+1] != 1){
                map[r][c] = 1;
                dfs(r,c+1,use_line_cnt + 1);
                map[r][c] = 0;
            }
        } // end of for c
        c_idx = 1;
    } // end of for r
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    ans = -1;
  
    cin >> col >> h >> row;
    
    for(int i=0; i<h; i++){
        int a,b;
        cin >> a >> b;
        map[a][b] = 1;
    }
    
    for(int i=0; i<4; i++){
        target_line = i;
        dfs(1,1,0);
        if(ans != -1)
            break;
    }
    cout << ans << endl;
    return 0;
}

Reivew

  • 544ms

  • 다시 푸니까 큰 문제 없이 풀었다.

  • 이번에는 목표 라인 수를 정해놓고 0 -> 3까지 DFS를 돌려서 시간을 단축시켰다.

[2] Answer Code (18. 10. 03)

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

int l[31][11]; // l is line
int row,col;
int ans = 2e9;

bool chk(){
    for(int i=1; i<=col; i++){
        int cp = i; // cp is column position
        int rp = 1; // rp is row position
        
        while (rp <= row) {
            if(l[rp][cp-1] == 1)
                cp--;
            else if(l[rp][cp] == 1)
                cp++;
            rp++;
        }
        if(cp != i)
            return false;
    }
    return true;
}

void dfs(int r, int c, int cnt){ // r is row, c is column, cnt is used line cnt
    if(cnt >= ans)
        return ;
    if( chk() ){
        ans = ans < cnt ? ans : cnt;
        return ;
    }
    if(cnt == 3 ) // [1]
        return ;
    for(int i=r; i<=row; i++){
        for(int j=1; j<=col-1; j++){
            if(l[i][j-1] == 1 || l[i][j] == 1 || l[i][j+1] == 1) continue;
            l[i][j] = 1;
            dfs(i,j, cnt+1 );
            l[i][j] = 0;
        }
    }
}

int main(){
    int n;
    cin >> col >> n >> row;
    
    for(int i=0; i<n; i++){
        int a,b;
        cin >> a >> b;
        l[a][b] = 1;
    }
    
    dfs(1,1,0);
    if( ans == 2e9)
        ans = -1;
    cout << ans << endl;
    return 0;
}

Review

  • 굉장히 어려웠다.

  • 막상 풀고나니까 명쾌하고 이런 유형에 대해서는 자신이 생긴 것 같다.

  • DFS 함수안 코드에 따라 시간이 확연히 다름을 알 수 있다.

if(cnt > 3 || cnt >= ans)
    return ;

if( chk() ){
    ans = ans < cnt ? ans : cnt;
    return ;
}

for(int i=r; i<=row; i++){
    for(int j=1; j<=col-1; j++){
        if(l[i][j-1] == 1 || l[i][j] == 1 || l[i][j+1] == 1) continue;
        l[i][j] = 1;
        dfs(i,j, cnt+1 );
        l[i][j] = 0;
    }
}

  • 996ms

  • if(cnt > 3 or cnt >= ans)처럼 하게 되면 cnt가 4가 되는 모든 경우를 살피게 된다.

  • 즉 cnt가 3일 때 chk()를 하고 조건을 충족시키지 못할 경우 바로 return을 해줘서 시간을 단축 시킬 수 있다.

  • 자세한건 아래 예시를 참고하자.

if( cnt >= ans)
    return ;

if( chk() ){
    ans = ans < cnt ? ans : cnt;
    return ;
}

if( cnt == 3 )
    return ;

for(int i=r; i<=row; i++){
    for(int j=1; j<=col-1; j++){
        if(l[i][j-1] == 1 || l[i][j] == 1 || l[i][j+1] == 1) continue;
        l[i][j] = 1;
        dfs(i,j, cnt+1 );
        l[i][j] = 0;
    }
}

  • 372ms

  • chk() 후 cnt == 3 일 경우에 cnt가 4가 될 경우를 가지치기한다.

  • 즉 cnt가 3일 때 chk()를 하였고 조건을 충족시키지 못했기 때문에 for loop를 돌기전에 return 시킨다.

if( cnt >= ans)
    return ;

if( chk() ){
    ans = ans < cnt ? ans : cnt;
    return ;
}

if( cnt == 3 )
    return ;

for(int i=r; i<=row; i++){
    for(int j=1; j<=col-1; j++){
        if(l[i][j-1] == 1 || l[i][j] == 1 || l[i][j+1] == 1) continue;
        l[i][j] = 1;
        dfs(r,c, cnt+1 ); // [1]
        l[i][j] = 0;
    }
}

  • 1972ms

  • [1] : 재귀 호출 시 매개 변수로 i,j가 아닌 r,c를 보내는 실수를 하였다.

[3] Wrong Code (18. 09. 24)

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

int l[272][32]; // l is line
int n,m;
int result;

bool chk(){
    int flag = 1;
    int st_x;
    int st_y;
    
    for(int i=1; i<=m; i++){
        if( ! flag )
            break;
        int v[272][32] = {0,}; // v is visit
        st_x = 1;
        st_y = i;
        v[st_x][st_y] = 1;
        
        /*
         좌우 있는지 체크
         없다면 아래로
         */
        while (1) {
            if(st_x == n+1){
                if(st_y != i){
                    flag = 0;
                }
                break;
            }
        
            if( l[st_x][st_y] && !v[st_x][st_y+1]){ // 오른쪽으로 생성된 라인이 있는가?
                v[st_x][st_y+1] = 1;
                st_y = st_y + 1;
            }
            else if( l[st_x][st_y-1] && !v[st_x][st_y-1]){ // 왼쪽으로 생성된 라인이 있는가?
                v[st_x][st_y-1] = 1;
                st_y = st_y - 1;
            }
            else{ // 좌우로 생성된 라인이 없으니 아래로 진행
                st_x ++;
                v[st_x][st_y] = 1;
            }
        } // end of while loop
    }
    return flag;
}


void print(){
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            cout << l[i][j] << " ";
        }
        cout << endl;
    }
}
int dfs(p pos, int dept){ // dept is depth
    bool ans = chk();
    if( dept >= result ) // 시간을 줄이기 위해 넣었지만 시간 초과를 해결하지 못했다.
        return -1;
    
    if(ans){
        return dept;
    }
    /*
     depth가 3일 때
     위에서 체크를 했고 그 값이 안되었기 때문에 return
     */
    if( dept >= 3){
        return -1;
    }
    
    // i means column
    // j means row
    int j = pos.first;
    for(int i=pos.second ; i<m; i++){
        for( ; j<=n; j++){
            if(l[j][i]) continue; // 이미 Line 존재
            if( l[j][i+1] != 0 || l[j][i-1] != 0) continue; // 좌우로 이미 연결된 라인이 있다면
            
            l[j][i] = dept + 6;
            /*
             1,3에 라인을 놓았다면
             그 다음 재귀에서는
             1,3 이후에 대해서만 체크를 하기 위해
             1,3을 위치값으로 넘깁니다.
             */
            int _tmp = dfs( p(j,i) , dept + 1);
            l[j][i] = 0;
            
            if( _tmp != -1 )
                return _tmp;
            
        } // end of for j
        if( j == n+1 )
            j = 1;
    } // end fo for i
    return -1;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int cnt;
    cin >> m >> cnt >> n;
    
    for(int i=0; i<cnt; i++){
        int a,b;
        cin >> a >> b;
        l[a][b] = 1;
    }
    
    result = 2e9;
    for(int col=1 ; col<m; col++){
        for(int row=1 ; row<=n; row++){
            int tmp = dfs(p(row,col),0);
            if(tmp != -1 && result > tmp)
                result = tmp;
        }
    }
    if( result == 2e9)
        result = -1;
    cout << result << endl;
    return 0;
}

Review

  • 18년 상반기 삼성 역량 테스트 2번 기출 문제.

  • 무려 2시간 30분 코딩을 했는데 틀렸다 !

  • TC는 다 맞는데 어디가 틀리는지 몰라서 질문을 했고 반례를 찾아서 수정을 했더니 시간 초과가 났다 !

  • 가지치기 없이 모든 조건을 탐색하기 때문에 시간 초과가 날 수 밖에 없다.

Recommend

Index