2020 KAKAO BLIND RECRUITMENT(자물쇠와 열쇠)

문제 유형

• 완전탐색

문제 접근

• 답
  • 열쇠가 자물쇠의 빈곳을 모두 채우면 true, 아니면 false 반환
• 주어지는 정보
  • 열쇠 크기 m(m ≤ 20)
  • 자물쇠 크기 n (n ≤ 20)
  • 홈 0, 돌기 1
• 후보
  • 완전탐색
    • 적합
      • 추정 연산 횟수 : (20204)(2020 + 20*20) = 1,280,000
      • 열쇠 4회전 * (자물쇠의 모든 좌표와 매칭 + 자물쇠의 빈 곳이 모두 없어지는 지 확인)
      • ⇒ 안정적인 연산 횟수로, 완전탐색 적합
• 설명
  • 열쇠 회전
    • key의 좌표를 읽는 시작 위치를 다르게 하면 90*n도 회전이 가능함
    • 예시(90도 회전)
      • y=0, x=0부터 읽는게 아닌, x=0, y=n-1부터 읽는 것

//90도 회전
for(int x = 0; x<n; x++){
    for(int y = n-1; y >= 0; y--){
        rotateBoard[i][j] = (board[y][x] == 1) ? 1 : 0;
        j++;
    }
    i++;
    j=0;
}

    //시계 방향(1~3) - 90도*n
    int[][] rotate(int choice, int[][] board){
        if(choice == 0){
            return board;
        }
        
        int n = board.length;
        
        int[][] rotateBoard = new int[n][n];
        
        int i = 0;
        int j = 0;
        if(choice == 1){
            for(int x = 0; x<n; x++){
                for(int y = n-1; y >= 0; y--){
                    rotateBoard[i][j] = (board[y][x] == 1) ? 1 : 0;
                    j++;
                }
                i++;
                j=0;
            }
        }
        
        else if(choice == 2){
            for(int y = n-1; y >= 0; y--){
                for(int x = n-1; x >= 0; x--){
                    rotateBoard[i][j] = (board[y][x] == 1) ? 1 : 0;
                    j++;
                }
                i++;
                j=0;
            }
        }
        
        else if(choice == 3){
            for(int x = n-1; x >= 0; x--){
                for(int y = 0; y < n; y++){
                    rotateBoard[i][j] = board[y][x];
                    j++;
                }
                i++;
                j=0;
            }
        }
        
        return rotateBoard;
    }

 

 

• 자물쇠 크기 확장
  • 열쇠는 자물쇠 좌표에서 벗어나도 됨
  • 따라서, 열쇠가 벗어나는 좌표까지 고려해서 자물쇠의 크기 확장
  • https://moonsbeen.tistory.com/90

int[][] sizeUpLock(int[][] key, int[][] lock){
    int n = lock.length;
    int m = key.length;
    
    int changeSize = n+(m-1)*2;
    int[][] changeLock = new int[changeSize][changeSize];
    
    int s = m-1;
    int e = m-1 + n-1;
    
    int i = 0;
    int j = 0;
    for(int y = s; y<=e; y++){
        for(int x = s; x<=e; x++){
            changeLock[y][x] = lock[i][j];
            j++;
        }
        j=0;
        i++;
    }
    return changeLock;
}

 

 

• 자물쇠에 열쇠 넣기
  • 자물쇠의 빈 홈에 열쇠를 채워넣음
  • (주의 : 자물쇠와 열쇠 좌표가 모두 돌기면 실패 처리 해야함)

int[][] fetchLock(int[][] key, int[][] lock, int y, int x){
    int n = lock.length;
    int m = key.length;
    
    int[][] newLock = new int[n][n];
    
    int i = 0;
    int j = 0;
    for(int curY = y; curY<y+m; curY++){
        for(int curX = x; curX<x+m; curX++){
            newLock[curY][curX] = key[i][j];
            j++;
        }
        j=0;
        i++;
    }
    
    int s = m-1;
    int e = n - m;
    for(int curY = s; curY<=e; curY++){
        for(int curX = s; curX<=e; curX++){
            if(lock[curY][curX] == 1){
                //key, lock이 서로 돌기면 0으로 처리
                newLock[curY][curX] = newLock[curY][curX] == 1 ? 0 : 1;
            }
        }
    }
    
    return newLock;
}

 

 

전체 코드

class Solution {
    
    //시계 방향(1~3) - 90도*n
    int[][] rotate(int choice, int[][] board){
        if(choice == 0){
            return board;
        }
        
        int n = board.length;
        
        int[][] rotateBoard = new int[n][n];
        
        int i = 0;
        int j = 0;
        if(choice == 1){
            for(int x = 0; x<n; x++){
                for(int y = n-1; y >= 0; y--){
                    rotateBoard[i][j] = (board[y][x] == 1) ? 1 : 0;
                    j++;
                }
                i++;
                j=0;
            }
        }
        
        else if(choice == 2){
            for(int y = n-1; y >= 0; y--){
                for(int x = n-1; x >= 0; x--){
                    rotateBoard[i][j] = (board[y][x] == 1) ? 1 : 0;
                    j++;
                }
                i++;
                j=0;
            }
        }
        
        else if(choice == 3){
            for(int x = n-1; x >= 0; x--){
                for(int y = 0; y < n; y++){
                    rotateBoard[i][j] = board[y][x];
                    j++;
                }
                i++;
                j=0;
            }
        }
        
        return rotateBoard;
    }


    public boolean checked(int[][] key, int[][] lock){
        int n = lock.length;
        int m = key.length;
        
        int s = m-1;
        int e = n - m;
        for(int curY = s; curY<=e; curY++){
            for(int curX = s; curX<=e; curX++){
                if(lock[curY][curX] == 0){
                    return false;
                }
            }
        }
        return true;
    }
    
    int[][] sizeUpLock(int[][] key, int[][] lock){
        int n = lock.length;
        int m = key.length;
        
        int changeSize = n+(m-1)*2;
        int[][] changeLock = new int[changeSize][changeSize];
        
        int s = m-1;
        int e = m-1 + n-1;
        
        int i = 0;
        int j = 0;
        for(int y = s; y<=e; y++){
            for(int x = s; x<=e; x++){
                changeLock[y][x] = lock[i][j];
                j++;
            }
            j=0;
            i++;
        }
        return changeLock;
    }

    int[][] fetchLock(int[][] key, int[][] lock, int y, int x){
        int n = lock.length;
        int m = key.length;
        
        int[][] newLock = new int[n][n];
        
        int i = 0;
        int j = 0;
        for(int curY = y; curY<y+m; curY++){
            for(int curX = x; curX<x+m; curX++){
                newLock[curY][curX] = key[i][j];
                j++;
            }
            j=0;
            i++;
        }
        
        int s = m-1;
        int e = n - m;
        for(int curY = s; curY<=e; curY++){
            for(int curX = s; curX<=e; curX++){
                if(lock[curY][curX] == 1){
                    //key, lock이 서로 돌기면 0으로 처리
                    newLock[curY][curX] = newLock[curY][curX] == 1 ? 0 : 1;
                }
            }
        }
        
        return newLock;
    }
    
    boolean resolve(int[][] key, int[][] lock){
        int n = lock.length;
        int m = key.length;
        
        for(int y = 0; y<n-(m-1); y++){
            for(int x = 0; x<n-(m-1); x++){
                for(int choice = 0; choice < 4; choice++){
                    int[][] curKey = rotate(choice, key);
                    int[][] curLock = fetchLock(curKey, lock, y, x);
                    if(checked(key, curLock) == true){
                        return true;
                    }
                }
            }
        }
        return false;
    }
    
    void printBoard(int[][] board){
        int n = board.length;
        for(int i = 0; i<n; i++){
            for(int j = 0; j<n; j++){
                System.out.print(board[i][j] + " ");
            }
            System.out.println();
        }
    }
    
    public boolean solution(int[][] key, int[][] lock) {
        boolean answer = true;
        
        lock = sizeUpLock(key, lock);
        answer = resolve(key,lock);
        

        return answer;
    }
}

 

 

실패

• 접근방법
  • 재귀 호출로 완전탐색
• 실패 이유
  • 재귀 방법이 잘못됐음
  • 열쇠가 모든 방향으로 움직이는 재귀 탐색을 실시했음
  • 하지만 열쇠가 좌표를 옮기고 난 후, 다음 재귀에서 다시 제자리로 복귀하는 예외 발생

class Solution {
    
    //시계 방향(1~3) - 90도*n
    int[][] rotate(int choice, int[][] board){
        if(choice == 0){
            return board;
        }
        
        int n = board.length;
        
        int[][] rotateBoard = new int[n][n];
        
        int i = 0;
        int j = 0;
        if(choice == 1){
            for(int x = 0; x<n; x++){
                for(int y = n-1; y >= 0; y--){
                    rotateBoard[i][j] = (board[y][x] == 1) ? 1 : 0;
                    j++;
                }
                i++;
                j=0;
            }
        }
        
        else if(choice == 2){
            for(int y = n-1; y >= 0; y--){
                for(int x = n-1; x >= 0; x--){
                    rotateBoard[i][j] = (board[y][x] == 1) ? 1 : 0;
                    j++;
                }
                i++;
                j=0;
            }
        }
        
        else if(choice == 3){
            for(int x = n-1; x >= 0; x--){
                for(int y = 0; y < n; y++){
                    rotateBoard[i][j] = (board[y][x] == 1) ? 1 : 0;
                    j++;
                }
                i++;
                j=0;
            }
        }
        
        return rotateBoard;
    }


    public boolean checkedKey(int[][] key){
        int m = key.length;
        for(int i = 0; i<m; i++){
            for(int j = 0; j<m; j++){
                if(key[i][j] == 1){
                    return true;
                }
            }
        }
        return false;
    }
    
    public boolean checked(int[][] key, int[][] lock){
        int n = lock.length;
        for(int i = 0; i<n; i++){
            for(int j = 0; j<n; j++){
                if(lock[i][j] == 0 && key[i][j] == 0){
                    return false;
                }
            }
        }
        return true;
    }
    
    //홀을 찾는 함수
    //key, lock 비교 함수
    //key, lock의 크기를 맞추는 함수
    
    void sizeUpKey(int[][] key, int[][] lock){
        int n = lock.length;
        int m = key.length;
        if(n == m || n < m){
            return;
        }
        
        int[][] newKey = new int[n][n];
        for(int i = 0; i<n; i++){
            for(int j = 0; j<n; j++){
                if(i >= m || j >= m){
                    continue;
                }
                
                newKey[i][j] = key[i][j];
            }
        }
        key = newKey;
    }
    
    int[][] moveKey(int choice, int[][] key){
        int[][] move = {{1,0},{0,1},{-1,0},{0,-1}};    
        int m = key.length;
        
        int[][] newKey = new int[m][m];
        
        for(int y = 0; y<m; y++){
            for(int x = 0; x<m; x++){
                int moveY = y + move[choice][0];
                int moveX = x + move[choice][1];
                
                if(moveY < 0 || moveY >= m || moveX < 0 || moveX >=m){
                    continue;
                }
                
                newKey[moveY][moveX] = (key[y][x] == 1) ? 1 : 0;
            }
        }
        
        return newKey;
    }
    
    boolean answer = false;
    void dfs(int[][] key, int[][] lock){
        if(checkedKey(key) == false){
            return;
        }
        
        for(int i = 0; i<4; i++){
            if(checked(rotate(i,key), lock) == true){
                answer = true;
                return;
            }
        }
 
        
        for(int i = 0; i<4; i++){
            dfs(moveKey(i, key), lock);
        }
    }
    
    public boolean solution(int[][] key, int[][] lock) {
        sizeUpKey(key, lock);
        dfs(key,lock);
        return answer;
    }
}