SHISENSHO 문제 질문입니다

  • yhb0730
    yhb0730

    사천성 문제를 풀다가 오답이 자꾸 나와서 질문 올립니다.
    제가 한 방법은 재귀함수를 써서 모든 좌표에서 상하좌우로 이동하면서 전체 판을 탐색하는 방식입니다.
    종료조건은 다음과 같은데요.

    1. 탐색을 시작한 판의 문자가 '.'(공백)일경우
    2. 4번 이상 꺾은 경우
    3. 판을 벗어난 경우 (row, col)
    4. '.'를 제외한 문자를 만난경우
      4-1. 시작 문자와 동일한 경우 벡터에 서로의 좌표를 넣고 탐색 종료
      4-2. 시작 문자와 다르거나 이미 탐색한(confirm함수) 좌표인경우 종료

      drift는 이전과 이동한 방향이 같은 경우는 증가하지않고 다른 경우는 증가합니다.
      confirm은 이미 찾은 좌표들이 벡터에 들어가있어서 탐색이 될 때마다 중복인지 검사하는 함수고요.

      생각한 대로 짠 코드는 이렇게 되있습니다. 제 생각에는 모든 판을 다 탐색하기 때문에 시관초과가 나올수는 있어도 오답은 안 나올거라고 생각했는데 오답이 나옵니다. 어디서 잘못된건지 찾지를 못해서 질문을 올립니다.

    #include<iostream>
    #include<vector>
    #include<utility>
    #include<math.h>
    using namespace std;
    
    
    bool Confirm(int row, int col);
    
    typedef struct coordinate
    {
        int x;
        int y;
    }Coord;
    
    class Board
    {
    private:
        int row;
        int col;
    public:
        char **board;
        void init_Board();
        void delete_Board();
        int search(char start, int row, int col, int drift, Coord before);
        int GetRow() { return this->row; }
        int GetCol() { return this->col; }
    };
    
    typedef struct CordCheck
    {
        int row;
        int col;
    }Ck;
    
    Coord cord[5] = { { -1, 0 },{ 1, 0 },{ 0, -1 },{ 0, 1 },{ 0, 0 } };
    
    Ck Fstart;
    
    pair<Ck, Ck> p;
    vector<pair<Ck, Ck>> v;
    
    void Board::init_Board()
    {
        int i, j;
        cin >> this->row >> this->col;
        this->board = new char*[row];
        for (i = 0; i < this->row; ++i)
        {
            this->board[i] = new char[col];
        }
    
        for (i = 0; i < this->row; ++i)
        {
            for (j = 0; j < this->col; ++j)
            {
                cin >> this->board[i][j];
            }
        }
    }
    
    void Board::delete_Board()
    {
        for (int i = 0; i < this->row; ++i)
        {
            delete[] this->board[i];
        }
        delete[] this->board;
        this->board = NULL;
        this->row = 0; this->col = 0;
    }
    
    int Board::search(char start, int row, int col, int drift, Coord before)
    {
        int i, flag = 0;
        /*가능한 경우인지 확인하는 부분 시작*/
        if (start == '.') return 0; //.인 경우 시작조차 안하도록 조치
        if (drift > 3) return 0;  //4번 이상 꺾은경우 종료
        if (row < 0 || row >= this->row) return 0; //판 벗어나면 종료
        if (col < 0 || col >= this->col) return 0; //판 벗어나면 종료
        if (this->board[row][col] == '.') {
            ;
        }
        else {
            if (this->board[row][col] == start) { //똑같은 문양 찾은 경우
                if (row != Fstart.row || col != Fstart.col) { //자기자신을 찾는 경우 제외 -> 이때 종료해버리면 시작할때 끝나버려서 그냥 계속 진행
                    if (Confirm(row, col)) return 0; //중복 검사
                    Ck temp = { row, col };
                    p = make_pair(Fstart, temp);
                    v.push_back(p);
                    return 1;
                }
            }
            else { return 0; } //다른 문양을 만난 경우 종료 -> 장애물 부딪힘
        }
        /*가능한 경우인지 확인하는 부분 끝 -> promising*/
    
    
        //this->board[row][col] = '/';
        int x, y;
        for (i = 0; i < 4; ++i)
        {
            x = before.x - cord[i].x; y = before.y - cord[i].y;
            if (!x && !y) { //똑같은 방향으로 움직인 경우 저번거랑 이번 움직임을 빼면 둘다 0
                flag += search(start, row + cord[i].y, col + cord[i].x, drift, cord[i]);
            }
            else if (abs(x) != 2 && abs(y) != 2) { //왔던길로 다시 가는 경우 둘 중 하나의 절대값은 2  
                flag += search(start, row + cord[i].y, col + cord[i].x, drift + 1, cord[i]);
            }
            else { ; }
        }
        //this->board[row][col] = '.';
        return flag;
    }
    
    
    int main(void)
    {
        int testcase, comb = 0;
        cin >> testcase;
        Board b;
        int i, j;
        for (int k = 0; k < testcase; ++k)
        {
            b.init_Board();
            for (i = 1; i < b.GetRow() - 1; ++i) {
                Fstart.row = i;
                for (j = 1; j < b.GetCol() - 1; ++j) {
                    Fstart.col = j;
                    comb += b.search(b.board[i][j], i, j, 0, cord[4]);
                }
            }
            cout << comb << endl;
            comb = 0;
            b.delete_Board();
            v.clear();
        }
        return 0;
    }
    
    bool Confirm(int row, int col) //똑같은거 순서 바꿔서 안 나오게 막아주는 함수
    { //생각해보니 중복탐색도 막아야함. 그것도 막음
        vector<pair<Ck, Ck>>::iterator iter;
        for (iter = v.begin(); iter != v.end(); ++iter) //순서가 바뀐경우니까 start가 second에 들어있음
        {
            if (Fstart.row == (*iter).second.row && Fstart.col == (*iter).second.col)
            {
                if (row == (*iter).first.row && (*iter).first.col)
                {
                    return true;
                }
            }
            if (Fstart.row == (*iter).first.row && Fstart.col == (*iter).first.col) //중복탐색인 경우 버림 -> 이걸 근본적으로 차단해야되는데 방법이 안 떠올라
            {
                if (row == (*iter).second.row && (*iter).second.col)
                {
                    return true;
                }
            }
        }
        return false;
    }
    

    7년 전
0개의 댓글이 있습니다.
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.