[ 백준 9944 ] NxM 보드 완주하기 (C++)

백준의 NxM보드 완주하기(9944) 문제이다.

[ 문제 바로가기 ]

[ 문제 풀이 ]

1) 본인은 이 문제를 공이 시작할 수 있는 모든 정점에서 모든 방향으로 진행해보는 완전탐색으로 진행해 보았다.

    먼저 전체적인 구현의 흐름은 다음과 같다.

    1. 어느 한 정점에서 특정 방향으로 공을 이동시킨다

    2. 이동시킨 공의 위치가 맵의 범위 내이고, 갈 수 있는 곳이고, 아직 방문하지 않은 곳이라면 그 이동시킨 정점에서

        같은 방향으로 또 이동시킨다.

    3. 2를 반복하다가, 맵의 범위를 벗어나거나, 이미 방문한 곳이거나, 갈 수 없는 곳이라면 현재 이동방향이 아닌

        다른 방향으로 궁을 다시한번 굴려본다.

    4. 2 ~ 3을 반복하다가, 방문한 칸의 갯수가 전체 빈곳의 갯수와 동일하다면 공을 굴린 최소의 횟수를 계산해준다.

    본인은 위의 과정을 재귀로 구현해 주었다. 먼저 재귀로 호출되는 함수의 매개변수는 총 5개가 존재한다.

    { 현재 공의 x 좌표 , y좌표 , 진행방향 , 방문한 칸의 갯수 , 공을 굴린 방향의 횟수 }

    방문한 칸의 갯수는 한 칸을 방문할 때 마다 +1 씩 되고, 공을 굴린 방향의 횟수는 현재 진행방향과 다른 방향으로 공을

    굴리게 될 경우에만 +1을 하게 된다.

    또한, Visit[][] 2차원 배열을 통해서 방문한 정점과 방문하지 않은 정점을 계속해서 체크해 주었는데, 만약 현재 길이

    잘못된 길이면 다른 길을 택해야 하는 백트래킹 방식으로 구현했기 때문에 한번 특정 길로 진행했다고 하더라도

    다시 방문 체크를 해제해 주는 과정 또한 필요하다.

[ 소스코드 ]

#include<iostream>
#include<cstring>
#include<vector>
 
#define endl "\n"
#define MAX 31
using namespace std;
 
int N, M;
int M_Area;
int Answer;
char MAP[MAX][MAX];
bool Visit[MAX][MAX];
vector<pair<int, int>> Dot;
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
void Initialize()
{
    memset(Visit, false, sizeof(Visit));
    memset(MAP, 0, sizeof(MAP));
    M_Area = 0;
    Answer = 987654321;
    Dot.clear();
}
 
void Input()
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> MAP[i][j];
            if (MAP[i][j] == '.')
            {
                Dot.push_back(make_pair(i, j));
                M_Area++;
            }
        }
    }
}
 
bool Range_Over(int x, int y)
{
    if (x < 0 || y < 0 || x >= N || y >= M) return true;    // 범위 밖을 벗어나면 true
    return false;
}
 
void Move(int x, int y, int d, int Cnt, int Turn_Cnt)
{
    if (Cnt == M_Area)
    {
        if (Answer > Turn_Cnt) Answer = Turn_Cnt;
        return;
    }
 
    int nx = x + dx[d];
    int ny = y + dy[d];
 
    if (Range_Over(nx, ny) == false && Visit[nx][ny] == false && MAP[nx][ny] == '.')
    {
        Visit[nx][ny] = true;
        Move(nx, ny, d, Cnt + 1, Turn_Cnt);
        Visit[nx][ny] = false;
    }
    else
    {
        for (int nd = 0; nd < 4; nd++)
        {
            if (nd == d) continue;
            nx = x + dx[nd];
            ny = y + dy[nd];
            
            if (Range_Over(nx, ny) == false && Visit[nx][ny] == false && MAP[nx][ny] == '.')
            {
                Visit[nx][ny] = true;
                Move(nx, ny, nd, Cnt + 1, Turn_Cnt + 1);
                Visit[nx][ny] = false;
            }
        }
    }    
}
 
void Solution()
{
    if (M_Area == 1)                        // Except Case 1 - Only One Dot
    {
        Answer = 0;
        return;
    }
    
    for(int i = 0 ; i < Dot.size(); i++)
    {
        int x = Dot[i].first;
        int y = Dot[i].second;
 
        for (int d = 0; d < 4; d++)
        {
            Visit[x][y] = true;
            Move(x, y, d, 1, 1);
            Visit[x][y] = false;
        }
    }    
}
 
void Solve()
{
    int Tc = 1;
    while (cin >> N >> M)
    {
        Initialize();
        Input();
        Solution();
 
        if (Answer == 987654321) Answer = -1;
        cout << "Case " << Tc << ": " << Answer << endl;
        Tc++;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}