9944번

9944번 - N*M 보드 완주하기

어떻게 풀지 고민하다가 그냥 완전탐색을 하는 방법으로 문제를 풀었다. 사실 움직이는 모습이 DFS와 유사하지만, 막힐 때까지 한쪽으로만 

쭉 움직인다는 점을 이용하면 문제를 풀 수 있다. 사실 완전탐색으로 풀려고 마음을 먹으면, 시간 복잡도를 우선적으로 판단해야 했다. N,M 

의 범위가 30이기 때문에 만약 DFS로 하면 시간초과가 날 수 있었지만, 이건 한쪽방향으로 쭉 이동하는 방식을 띄기 때문에 정확하게 판단은 못해도 시간이 꽤나 많이 단축될 것 같아서 완전탐색을 시도했다.

이 문제의 더 많은 테스트케이스는 -> https://ncna-region.unl.edu/ 

문제를 풀면서 예외케이스가 있었는데 바로 맵 전체에서 딱 한칸만 비어있는 경우였다. 나는 처음에 이 경우는 1로 처리를 했었는데, 테스트케이스에서 보니 정답은 0으로 되어있었다. 이 부분은 좀 오해의 소지가 있을 것 같다. 원본 문제를 보지는 않았지만..

아무튼 저 경우를 예외로 처리해주면 문제를 풀 수 있었다.

<정답 코드>

#include<iostream>
using namespace std;
#define INF 987654321
#define MAX 31
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int N, M, ans = INF;
char map[MAX][MAX];
int visited[MAX][MAX];
 
void init()
{
    ans = INF;
    for (int i = 0; i < MAX; i++)
    {
        for (int j = 0; j < MAX; j++)
        {
            visited[i][j] = 0;
        }
    }
}
void go(int x, int y,int dir, int move)
{
    int cnt = 0;
    visited[x][y] = 1;
 
    //사방이 막혀있는지 확인
    for (int d = 0; d < 4; d++)
    {
        int nx = x + dx[d];
        int ny = y + dy[d];
        if (nx < 0 || ny < 0 || nx >= N || ny >= M || map[nx][ny] == '*' || visited[nx][ny] != 0)
            cnt++;
    }
 
    //사방이 막혀있으면 
    if (cnt == 4)
    {
        bool finish = true;
        // 맵 전체를 보면서 전체를 모두 방문했는지 확인
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < M; j++)
            {
                if (map[i][j] == '.' && visited[i][j] == 0)
                {
                    finish = false;
                    break;
                }
            }
            if (!finish)
                break;
        }
 
        // 맵 전체를 방문했으면 결과값 찾기
        if (finish && ans > move)
            ans = move;
 
        visited[x][y] = 0;
        return;
    }
 
    int nx = x + dx[dir];
    int ny = y + dy[dir];
 
    //다음 이동점이 움직일 수 없는 곳일때
    if (nx < 0 || ny < 0 || nx >= N || ny >= M || map[nx][ny] == '*' || visited[nx][ny] == 1)
    {
        // 내가 지금 가진 방향 말고 다른 방향 찾기
        for (int d = 0; d < 4; d++)
        {
            int nxx = x + dx[d];
            int nyy = y + dy[d];
            // 새로 찾은 방향으로 움직일 수 있는지 확인
            if (d != dir && nxx>=0 && nyy>=0 && nxx<N && nyy<M && visited[nxx][nyy]==0 && map[nxx][nyy]=='.')
            {
                go(x, y, d, move + 1);
            }
        }
    }
    // 다음 점이 이동할 수 있을 때
    else {
        //예외사항 : 맵에서 움직일 수 있는 칸이 한개일 때
        if (move == 0)
            move = 1;
        go(nx, ny, dir, move);
    }    
    visited[x][y] = 0;
    return;
 
}
int main()
{
    //freopen("input.txt", "r", stdin);
    
    int cnt = 0;
    while (cin >> N >> M)
    {
        init();
        cnt++;
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < M; j++)
            {
                cin >> map[i][j];
            }
        }
 
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < M; j++)
            {
                if (map[i][j] != '*') {
 
                    for (int d = 0; d < 4; d++)
                    {
                        go(i, j, d, 0);
                    }
                }
            }
        }
 
        // 맵 전체를 다 갈 수 없을 때
        if (ans == INF)
            ans = -1;
 
        cout <<"Case "<<cnt<<": "<< ans << endl;
    }
 
    return 0;
}