Flag Clear

길찾기 알고리즘에 있어서 이런 일이 흔히 생길 수 있습니다.

class Cell
{
private :
    bool isChecked = 0;
    bool canEnter;
    int coordX, coordY;
public :
    void Reset()
    {
        isChecked = false;
    }

    bool Search(Cell field[2048][2048], int goalX, goalY)
    {
        if(!canEnter)
            return false;
        if(goalX == coordX && goalY == coordY)
            return true;
        if(!isChecked)
        {
            isChecked = true;
            return field[CoordX + 1][CoordY].Search(field, goalX, goalY) ||
                   field[CoordX - 1][CoordY].Search(field, goalX, goalY) ||
                   field[CoordX][CoordY + 1].Search(field, goalX, goalY) ||
                   field[CoordX][CoordY - 1].Search(field, goalX, goalY);
        }
    }
};

class Building
{
private :
    Cell field[2048][2048];
public :
    bool CanGoTo(int fromX, int fromY, int toX, int toY)
    {
        for(int x = 0; x < 2048; ++x)
            for(int y = 0; y < 2048; ++y)
                field[x][y].Reset();   // 이전 탐색결과 지우기
        return field[fromX][fromY].Search(field, toX, toY);
};

매번 길을 찾기 전에 필드의 모든 셀에 대해 이전에 찾았던 길의 정보를 지워야 하죠.

그런데 위와 같이 모든 셀에 대해 플래그를 지우는데 약간의 시간이 지체될 수 있습니다. 2048 * 2048 = 4194304개의 셀에 대해 작업을 해야 하거든요.

이것을 이렇게 하면 어떨까요?

class Cell
{
public :
    static unsigned long currentChecked = 0;
private :
    unsigned long isChecked;
    bool canEnter;
    int coordX, coordY;
public :
    bool Search(Cell field[2048][2048], int goalX, goalY)
    {
        if(!canEnter)
            return false;
        if(goalX == coordX && goalY == coordY)
            return true;
        if(isChecked != currentChecked)
        {
            isChecked = currentChecked;
            return field[CoordX + 1][CoordY].Search(field, goalX, goalY) ||
                   field[CoordX - 1][CoordY].Search(field, goalX, goalY) ||
                   field[CoordX][CoordY + 1].Search(field, goalX, goalY) ||
                   field[CoordX][CoordY - 1].Search(field, goalX, goalY);
        }
    }
};

class Building
{
private :
    Cell field[2048][2048];
public :
    bool CanGoTo(int fromX, int fromY, int toX, int toY)
    {
        ++Cell::currentChecked;   // 이전 탐색결과 지우기
        return field[fromX][fromY].Search(field, toX, toY);
};




currentChecked를 바꾸는 것만으로 2048*2048개 모든 Cell의 isChecked가 갱신됩니다. currentChecked와 isChecked의 값이 같은지 다른지가 중요하므로 currentChecked에 오버플로우가 일어나도 상관이 없죠.

다만 한가지 문제는, 어느 한 셀이 0xFFFFFFFF회 동안 한번도 참조되지 않는다면 그 셀은 isChecked가 true인 상태가 된다는 것입니다.

이럴 가능성이 없거나, 무시해도 된다면 상관없지만, 이럴 가능성을 무시할 수 없다면 다음과 같은 추가코드가 필요해집니다.

class Cell
{
public :
    static unsigned long currentChecked = 0;
private :
    unsigned long isChecked = 0;
    bool canEnter;
    int coordX, coordY;
public :
    void Reset()
    {
        isChecked = 0;
    }

    bool Search(Cell field[2048][2048], int goalX, goalY)
    {
        if(!canEnter)
            return false;
        if(goalX == coordX && goalY == coordY)
            return true;
        if(isChecked != currentChecked)
        {
            isChecked = currentChecked;
            return field[CoordX + 1][CoordY].Search(field, goalX, goalY) ||
                   field[CoordX - 1][CoordY].Search(field, goalX, goalY) ||
                   field[CoordX][CoordY + 1].Search(field, goalX, goalY) ||
                   field[CoordX][CoordY - 1].Search(field, goalX, goalY);
        }
    }
};

class Building
{
private :
    Cell field[2048][2048];
public :
    bool CanGoTo(int fromX, int fromY, int toX, int toY)
    {
        // 이전 탐색결과 지우기
        if(Cell::currentChecked == 0xFFFFFFFF)
        {
            // 오버플로우 나기 전에 초기화
            ++Cell::currentChecked
            for(int x = 0; x < 2048; ++x)
                for(int y = 0; y < 2048; ++y)
                    field[x][y].Reset();
            
        }
        else
            ++Cell::currentChecked;
        return field[fromX][fromY].Search(field, toX, toY);
};