[틀림] 프로그래머스 자물쇠와 열쇠 // 배열회전, 배열좌표

https://school.programmers.co.kr/learn/courses/30/lessons/60059

프로그래머스

시도1

lock 의 y,x에 좌물쇠를 대보면서 전부 1인지 체크하는 방법

오답포인트 : 자물쇠, 열쇠 둘다 (0,0)에서 시작한다고 가정

반례 : 열쇠가 좌물쇠 좌측위에 있는경우도 가능함.

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> key, loc, origin;

vector<vector<int>> rot(vector<vector<int>> origin){
    vector<vector<int>> ret(24, vector<int>(24, 0));
    // int ret[24][24];
    for(int i=0;i<key.size();++i){
        for(int j=0;j<key[0].size();++j){
            ret[i][j]=origin[key.size()-j-1][i];
        }
    }
    return ret;
}

// lock의 모든좌표에서 v 배열로 덮어지는지
// void go(int y, int x, vector<vector<int>>& v){
//     for(int i=0;i<lock.size();++i){
//         for(int j=0;j<lock[0].size();++j){
//             dfs(i,j);
//         }
//     }
// }

//전부 채워졌는지
int check(vector<vector<int>>& lock){
    for(int i=0;i<lock.size();++i){
        for(int j=0;j<lock[0].size();++j){
            if(lock[i][j]==0) return 0;
        }
    }
    return 1;
}

//y,x 에 자물쇠(v)를 대보기
int dfs(int y, int x, vector<vector<int>>& v){
    //원복
    loc = origin;
    for(int i=0;i<key.size();++i){
        for(int j=0;j<key[0].size();++j){
            //범위쳌
            if(y+i >= loc.size() || x+i >= loc[0].size()){
                continue;
            }
            //겹치는건 안됨
            if(loc[y+i][x+j]==1 && v[i][j]==1){
                return 0;
            }
            if(loc[y+i][x+j]==0 && v[i][j]==1){
                loc[y+i][x+j]=1;
            }
        }
    }
    
    for(int i=0;i<loc.size();++i){
        for(int j=0;j<loc[0].size();++j){
            cout<<loc[i][j]<<" ";
        }cout<<"\n";
    }
    
    if(check(loc)){
        return 1;
    }
    return 0;
}

bool solution(vector<vector<int>> _key, vector<vector<int>> _lock) {
    key=_key;
    loc=_lock;
    origin = _lock;
    bool answer = true;
    
    vector<vector<int>> tmp1 = rot(key);
    vector<vector<int>> tmp2 = rot(tmp1);
    vector<vector<int>> tmp3 = rot(tmp2);
    
//     for(int i=0;i<key.size();++i){
//         for(int j=0;j<key[0].size();++j){
//             cout<<tmp1[i][j]<<" ";
//         }cout<<"\n";
//     }
    
//     for(int i=0;i<key.size();++i){
//         for(int j=0;j<key[0].size();++j){
//             cout<<tmp2[i][j]<<" ";
//         }cout<<"\n";
//     }
    
//     for(int i=0;i<key.size();++i){
//         for(int j=0;j<key[0].size();++j){
//             cout<<tmp3[i][j]<<" ";
//         }cout<<"\n";
//     }
    
    for(int i=0;i<loc.size();++i){
        for(int j=0;j<loc[0].size();++j){
            if(dfs(i,j, tmp1)){
                return 1;
            }
            if(dfs(i,j, tmp2)){
                return 1;
            }
            if(dfs(i,j, tmp3)){
                return 1;
            }
            if(dfs(i,j, key)){
                return 1;
            }
        }
    }
    
    // dfs(1,1,tmp1);
    
    return 0;
}

 

 

정답풀이

행동영역 : 복잡한 배열문제는 격자를 그리고, 식을 찾아라.

큰 배열(arr)을 두고, lock을 중앙에두고 자물쇠를 대보는 것까지는 추론완료.

lock을 중앙에 어떻게 복사할까? 

그림을 그려서 offset이라는 규칙을 찾아내야함. 

for(i=0 ~ lock.size())

     arr[i+offset] = lock[i][j]

key의 시작좌표 (y,x)의 범위는 어디까지?

n+offset 까지

그림을 그려서 선분의 길이가 n+offset임을 찾아야함.

원본배열에 어떻게 더하지?

식을세우고, 그림으로 돌려보면서 검증하였음.

for(i=0 ~ key.size())

     arr[y+i] += key[i][j]

더한값이 모두 1인경우에만 유효, 겹치는경우는 값이 2가됨.

arr을 넉넉한 크기로 잡았으므로, 범위초과를 신경쓸 필요 없음.

알고리즘을 정리하면

key를 대볼수있는 좌표 (y,x)에 대해

key를 4방향 회전하면서

arr 중앙에 lock원본을 복사하고

key의 값을 arr에 더함

중앙의 lock 범위가 모두1이면 통과

 

코드

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> key, loc, origin;
int arr[64][64];

vector<vector<int>> rot(vector<vector<int>> origin){
    vector<vector<int>> ret(24, vector<int>(24, 0));
    // int ret[24][24];
    for(int i=0;i<key.size();++i){
        for(int j=0;j<key[0].size();++j){
            ret[i][j]=origin[key.size()-j-1][i];
        }
    }
    return ret;
}

bool solution(vector<vector<int>> _key, vector<vector<int>> _lock) {
    key=_key;
    loc=_lock;
    origin = _lock;
    int n=_lock.size();
    int m= key.size();
    bool answer = true;
    
    vector<vector<int>> tmp1 = rot(key);
    vector<vector<int>> tmp2 = rot(tmp1);
    vector<vector<int>> tmp3 = rot(tmp2);
    
//     for(int i=0;i<key.size();++i){
//         for(int j=0;j<key[0].size();++j){
//             cout<<tmp1[i][j]<<" ";
//         }cout<<"\n";
//     }
    
//     for(int i=0;i<key.size();++i){
//         for(int j=0;j<key[0].size();++j){
//             cout<<tmp2[i][j]<<" ";
//         }cout<<"\n";
//     }
    
//     for(int i=0;i<key.size();++i){
//         for(int j=0;j<key[0].size();++j){
//             cout<<tmp3[i][j]<<" ";
//         }cout<<"\n";
//     }
    
    int offset = m-1;
    for(int y=0;y<offset + n;++y){
        for(int x=0;x<offset + n;++x){
            for(int k=0;k<4;++k){ //for 회전
                memset(arr,0,sizeof(arr)); //초기화
                vector<vector<int>> key;
                if(k==0){
                    key = _key;
                }
                else if(k==1){
                    key = tmp1;
                }
                else if(k==2){
                    key = tmp2;
                }
                else if(k==3){
                    key = tmp3;
                }
                //arr중앙에 lock을 복사
                for(int i=0;i<n;++i){
                    for(int j=0;j<n;++j){
                        arr[i+offset][j+offset]=_lock[i][j];
                    }
                }

                //채우기 (덧셈이용)
                for(int i=0;i<m;++i){
                    for(int j=0;j<m;++j){
                        arr[y+i][x+j]+=key[i][j];
                    }
                }

                int allOne=1;
                //arr 중앙에 lock부분이 모두 1이면 ok
                for(int i=0;i<n;++i){
                    for(int j=0;j<n;++j){
                        if(arr[i+offset][j+offset]!=1){
                            allOne=0;
                            break;
                        }
                    }
                }
                if(allOne) return 1;
                // key = rot(key);
            }
            // key = rot(key); //360도 원복
        }
    }
    
    // dfs(1,1,tmp1);
    
    return 0;
}

 

 

기타 까먹은 문법들

2차원 벡터 초기화 방법

vector<vector<int>> ret(24, vector<int>(24, 0));

배열 회전시 ret배열을 두고, 원본을 ret에 복사하는 것임.

vector<vector<int>> rot(vector<vector<int>> origin){
    vector<vector<int>> ret(24, vector<int>(24, 0));
    for(int i=0;i<key.size();++i){
        for(int j=0;j<key[0].size();++j){
            ret[i][j]=origin[key.size()-j-1][i];
        }
    }
    return ret;
}