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

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

9944번: NxM 보드 완주하기

 

 

 

[난이도] Gold3
[유형] 백트래킹

[풀이]
N과 M제한이 30이지만 모든 점에서 4방향으로 가는 재귀함수를 호출하면 시간초과가 날 것이다.
하지만 현재 가고 있는 방향 d도 인자로 전달해서 d로 갈수 있다면 나머지 3 방향은 체크할 필요가 없이
d로 진행하면 된다.
즉, 방향을 바꿔야 하는 곳에서만 갈 수 있는 곳으로 재귀함수를 호출해주면 되므로
많은 케이스가 프루닝되어 시간내에 문제를 해결할 수 있다.

 

 

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int dy[5]={-1,1,0,0,1000};
int dx[5]={0,0,1,-1,1000};
int N,M,total,ans,inf=987654321;
char map[31][31];
bool visit[31][31];
bool check(int y,int x,int d){
    int ny=y+dy[d];
    int nx=x+dx[d];
    return !(ny<0||nx<0||ny>=N||nx>=M||map[ny][nx]=='*'||visit[ny][nx]);
}
void sol(int y,int x,int d,int cnt,int t){
    visit[y][x]=1;
    if(t==total){
        ans=min(ans,cnt);
        visit[y][x]=0;
    }
    if(check(y,x,d)){
        sol(y+dy[d],x+dx[d],d,cnt,t+1);
    }else{
        for(int i=0;i<4;i++){
            if(check(y,x,i)){
                sol(y+dy[i],x+dx[i],i,cnt+1,t+1);
            }
        }
    }
    visit[y][x]=0;
}

int main(){
    int s=0;
    while(scanf("%d%d",&N,&M)!=-1){
        memset(map,0,sizeof(map));
        ans=inf;
        total=0;
        for(int i=0;i<N;i++)
            for(int j=0;j<M;j++) {
                scanf(" %c",&map[i][j]);
                if(map[i][j]=='.') total++;      
            }
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                if(map[i][j]=='.'){
                    memset(visit,0,sizeof(visit));
                    sol(i,j,4,0,1);
                }
            }
        }
        if(ans==inf) ans=-1;
        printf("Case %d: %d\n",++s,ans);
    }
}

 

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold3/9944.cpp