[Algorithm]Baekjoon 9944번 :: NxM 보드 완주하기

https://www.acmicpc.net/problem/9944

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_set>
#include <thread>
#include <atomic>
 
using namespace std;
 
int t, n, m;
string s;
char arr[31][31];
int dirs[4][2] = { {-1,0},{1,0}, {0,-1}, {0,1} };
const int maxNum = 0x3f3f3f3f;
int curMoveCount, answer;
int dotCount = 0;
 
int GetReverseDir(int dir)
{
    switch (dir)
    {
    case 0: return 1;
    case 1: return 0;
    case 2: return 3;
    case 3: return 2;
    default: return -1;
    }
}
 
bool IsValid(int y, int x)
{
    if (y < 0 || y == n) return false;
    if (x < 0 || x == m) return false;
    if (arr[y][x] == '*') return false;
 
    return true;
}
 
int Move(int y, int x, int dir)
{
    int moveCount = 0;
 
    while (1)
    {
        y += dirs[dir][0];
        x += dirs[dir][1];
 
        if (IsValid(y, x))
        {
            ++moveCount;
            arr[y][x] = '*';
        }
        else break;
    
    }
 
    return moveCount;
}
 
void Restore(int y, int x, int dir, int moveCount)
{
    while (moveCount--)
    {
        arr[y][x] = '.';
 
        y += dirs[dir][0];
        x += dirs[dir][1];
    }
}
 
 
void DFS(int y, int x)
{
    if (dotCount == 0)
    {
        answer = min(answer, curMoveCount);
        return;
    }
 
    for (int dir = 0; dir < 4; ++dir)
    {
        int moveCount = Move(y, x, dir);
 
        if (moveCount == 0) continue;
 
        int nextY = y + dirs[dir][0] * moveCount;
        int nextX = x + dirs[dir][1] * moveCount;
        
        ++curMoveCount;
        dotCount -= moveCount;
 
        DFS(nextY, nextX);
 
        // 복구
        Restore(nextY, nextX, GetReverseDir(dir), moveCount);
        --curMoveCount;
        dotCount += moveCount;
    }
}
 
 
vector<int> answers;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
 
    while (cin >> n >> m)
    {
        answer = maxNum;
        dotCount = 0;
        curMoveCount = 0;
 
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < m; ++j)
            {
                cin >> arr[i][j];
                if (arr[i][j] == '.') ++dotCount;
            }
        }
 
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < m; ++j)
            {
                if (arr[i][j] == '.')
                { 
                    --dotCount;
                    arr[i][j] = '*';
 
                    DFS(i, j);
 
                    ++dotCount;
                    arr[i][j] = '.';
                }
            }
        }
 
        if (answer == maxNum) answers.push_back(-1);
        else answers.push_back(answer);
    }
    
 
    for (int i = 0; i < answers.size(); ++i)
    {
        printf("Case %d: %d\n", i + 1, answers[i]);
    }
}
 
 

 

기본적인 형태는 완전탐색. 다만, 한쪽루트로 뚫고 다시 다른 루트탐색하기전에 복구를 잘 해놔야한다.

 

꼭 이런거하면 인덱스계산이 헷갈린다..

위 코드처럼 끝까지 갈수있는곳 찾아서 한번에 건너뛰거나, 아니면 한칸씩 현재방향으로 끝까지 가다가 벽에 부딪혔을때 그때 4방향에 대해 뻗어나가면 된다.

 

한번에 건너뛰는게, 복구하기가 편해서 나는 한번에 건너뛰었다.