BOARDCOVER self review

Question

BOARDCOVER self review

Opened this issue 4 years ago · 0 comments

dakyommii commented 4 years ago

BOARDCOVER self review

파일명: BOARDCOVER/dakyommii.cpp

수행시간: 0ms

1. 문제 해결 과정

1차 시도: for루프를 돌면서 0인 지점(도형이 없는 부분)을 찾아 그 위치로부터 4가지 모양으로 보드를 채울 수 있는지 검사해야 한다는 것을 파악했지만, for루프만 사용하는 방법을 생각하다보니 한 위치로부터 여러 모양이 가능한지 검사하는 것과 해당 자리에 들어갈 수 없는 모양이 생길 경우 되돌아가는 방법에 대해 생각해내지 못해서 실패했습니다.
2차 시도: 재귀를 사용해서 여러 모양이 가능한지 검사하고 되돌아가기도 가능할 수 있도록 구현했습니다. 그리고 1차 시도에는 여러 모양이 가능한지 그 위치로부터 탐색하는 것을 for문으로 돌리려고 했지만, 도형의 모양은 항상 고정적이라는 점을 활용해 먼저 도형의 모양을 좌표 배열로 만들고 해당 모양을 테스트할 때 검사할 위치 좌표로 활용했습니다.

2. 아이디어

보드판에 놓을 수 있는 4가지 형태의 도형의 좌표 구하기
보드판에 도형을 놓을 수 있는지 검사(벽에 부딪힐 경우, 다른 도형과 겹칠 경우 확인)
보드판 자리 탐색하면서 비어 있으면 그 위치에 도형 놓아보기
3-1. 도형 놓아보고 도형을 놓을 수 없는 위치이면 놓았던 도형 삭제하기
도형으로 보드판 채우면 count 세기

3. 코드 설명

#include <iostream>
using namespace std;

//보드크기 = H*W
int H, W;
int board[20][20];

//채울 도형 모양 고정
int shapes[4][3][2] { {{0,0},{1,0},{0,1}},{{0,0},{1,0},{1,1}},{{0,0},{0,1},{1,1}},{{0,0},{1,0},{1,-1}}};

position: (y,x)에 대해 도형 놓을 수 있는 위치인지 검사하는 메소드

전달받은 (y,x) 좌표에 for문으로 모양 바꿔가면서 도형 놓을 수 있는지 각 모양에 해당하는 좌표 더해서 검사 ➡️ 검사하려는 좌표가 도형에서 (0,0) 위치에 있는 것
도형 놓을 수 없는 위치일 경우 false 반환해 도형 삭제하도록 함
2-1. 다른 도형과 겹칠 경우: 도형 놓는 메소드로부터 도형 놓을 경우 1, 도형 삭제할 경우 -1 전달 받아 전달 받은 위치에 넣으면 도형 겹치면 2, 도형이 없었는데 도형 놓으면 1, 도형 놓았는데 삭제하면 0이 되므로 겹칠 경우인 2이면 false 반환
2-2. 보드 벗어날 경우

bool position(int y, int x, int shape, int a) {   //도형 놓을 수 있는 위치인지 검사
    bool chk = true;    //도형 놓을 수 있는 위치
    
    //검사할 좌표
    for (int i = 0; i < 3; i++) {
        int cy = y + shapes[shape][i][0];
        int cx = x + shapes[shape][i][1];
        
        //도형 놓을 수 없는 위치일 경우 false 반환해 도형 삭제하도록 함
        //다른 도형이랑 겹침->여기서 해당 자리 1로 채우기
        if((board[cy][cx] += a) > 1) chk = false;
        //보드 벗어남
        else if(cx < 0 || cy < 0 || cx >= W || cy >= H) chk = false;
    }
   
    return chk;
}

cover: 도형 놓는 메소드

보드판 좌표 돌면서 비어 있는 위치(0) 탐색
비어 있으면 x,y에 H,W값 업데이트해서 position으로 전달
보드판 모드 채워진 경우 x,y값이 -1에서 업데이트되지 않으므로 이 경우 보드판을 모두 채운 하나의 경우가 되므로 1 return
for문 돌면서 4가지의 도형이 놓일 수 있는지 검사
4-1. position으로 1 전달해서 도형 놓도록 해서 도형 놓을 수 있으면 재귀로 cover() 호출해 다음 위치 탐색해서 보드판 모두 채울 때까지 똑같은 과정 반복
4-2. 보드판 다 채우면 if문 나와서 다른 모양도 가능한지 검사하기 위해 -1 position으로 전달해 해당 위치에 도형 삭제함(되돌리기 과정)
보드판 다 채운 경우 외에 position으로 1 전달했을 때 false return된 경우(도형 놓을 수 없는 경우)도 다른 모양 시도해보기 위해 되돌리기 과정 실행
위 과정 반복해 for문으로 탐색했을 때 모든 위치 1로 채워지면 count return

int cover() {
    int x = -1, y = -1; //x, y 초기화
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            if(board[i][j] == 0) {  //비어 있으면 x,y에 업데이트해서 도형 올 수 있는 위치인지 검사
                y = i;
                x = j;
                break;
            }
        }
        if (y != -1) {  //(i,j)가 0인 좌표 존재하는 경우 for문 나오기
            break;
        }
    }
    
    if (y == -1) {  //보드판 다 채워진 경우 return하면 count값에 추가되어 방법이 하나 느는 것
        return 1;
    }
    
    int count = 0;  //도형 놓는 방법 수
    for (int shape = 0; shape < 4; shape++) {
        if(position(y, x, shape,1)) { //도형 놓을 수 있는 위치일 경우
            //cover() 재귀하면 현위치에는 이미 채워졌으므로 다음 칸부터 검사함
            //보드판 다 채울 때까지 재귀호출해서 다 채우면 1 return해 count 증가
            count += cover();
        }
        
        //이 경우는 현 위치에 도형 놓을 수 없을 경우나 현재 도형으로 계속 재귀호출하면서 진행한 결과 보드 채우는 방법 몇 가지 알아낸 경우 다른 모양으로도 방법 count하려는 것
        //다른 모양 도형도 가능한지 확인하기 위해 현위치에서 앞선 모양으로 덮은 블록 지움
        position(y, x, shape,-1);
    }

    return count;
}

입출력

int main() {

    //입력
    //케이스
    int C;
    cin >> C;
    
    //게임판 입력
    char s[20];
    for (int k = 0; k < C; k++) {
        cin >> H >> W;
        for (int i = 0; i < H; i++) {
            cin >> s;
            for (int j = 0; j < W; j++) {
                
                //도형 채워진 곳은 1, 아닌 곳은 0으로 채우기
                board[i][j] = (s[j] == '#') ? 1 : 0;
            }
        }
        //출력
        cout << cover() << endl;
    }    
}