백준 9944번 - NxM보드 완주하기 (C++)

문제

해결 방법

입력 시, *의 갯수를 카운팅하고, 내부에서 DFS를 통하여 구현하였다. 내부 작동 중 .을 *로 바꾸는 횟수를 카운팅하여 최종*의 갯수가 NxM의 갯수가 되면 리턴하였다. 또한, 백트래킹을 이용하여 롤백을 구현하였으며, 외 특별한점은 없다.

 

아쉬웠던 점

없음

 

코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
pair<int, int> RLUD[4] = { {0,1}, {0,-1}, {1,0}, {-1,0} };
int N, M, Ret=-1;
 
int NmBoard(char _MapVec[][30], int _i, int _j, int Count, int _DotCount)
{
    if (_DotCount == 0)
        Ret = Count;
    _MapVec[_i][_j] = '*';
 
    for (int i = 0; i < 4; ++i)
    {
        int _ii = _i + RLUD[i].first, _jj = _j + RLUD[i].second;
        if (_ii >= 0 && _jj >= 0 && _ii < N && _jj < M && _MapVec[_ii][_jj] == '.')
        {
            while (true)
            {
                if (!(_ii >= 0 && _jj >= 0 && _ii < N && _jj < M) || _MapVec[_ii][_jj] == '*')
                {
                    NmBoard(_MapVec, _ii -= RLUD[i].first, _jj -= RLUD[i].second,Count+1, _DotCount);
                    while (_ii != _i || _jj != _j)
                    {
                        _MapVec[_ii][_jj] = '.';
                        _DotCount++;
                        _ii -= RLUD[i].first;
                        _jj -= RLUD[i].second;
                    }
                    break;
                }
                else if(_ii >= 0 && _jj >= 0 && _ii < N && _jj < M)
                {
                    _MapVec[_ii][_jj] = '*';
                    _DotCount--;
                }
                _ii += RLUD[i].first;
                _jj += RLUD[i].second;
            }
        }
    }
 
   return Ret;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int Case = 1;
        
    while (cin >> N >> M)
    {
        char MapVec[30][30];
        int Max = 1000001, DotNum = 0;
        for (int i = 0; i < N; ++i)
            for (int j = 0; j < M; ++j)
            {
                cin >> MapVec[i][j];
                if (MapVec[i][j] == '.')
                    DotNum++;
            }
 
        for (int i = 0; i < N; ++i)
            for (int j = 0; j < M; ++j)
                if (MapVec[i][j] == '.')
                {
                    int Num = NmBoard(MapVec, i, j, 0, DotNum-1);
                    MapVec[i][j] = '.';
                    if (Num < Max && Num != -1) Max = Num;
                    Ret = -1;
                }
 
        if (Max == 1000001) Max = -1;
        cout << "Case " << Case << ": " << Max << endl;
        Case++;
    }
}

입력 -> DFS(24~31번줄 백트래킹) 외 특이사항 없음

 

잡설 : 풀었는데 시간이 너무 높게 나와서 이유를 봤더니 굳이굳이 벡터를 쓰던 습관 때문이였다... 벡터만 3030배열로 바꾸어주니, 시간이 2044ms에서 132ms로 단축되었다.