[BOJ/백준][Gold4] 5913 : 준규와 사과 (C++)

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

5913번: 준규와 사과

 

 

[난이도] Gold4
[유형] 브루트포스

[풀이]
map이 5x5이므로 전부 해보자는 생각으로 모든 케이스를 직접 구했다.
(1,1)에서 사과가 있는 (y,x)로 조건을 만족하며 갈 수 있는 모든 경로에 대해서
(y,x)에서 다시 (5,5)로 갈 수 있는 모든 경로중에 조건을 만족하는 케이스를 모두 더하면 된다.
조건 : (1,1)->(y,x) , (y,x)->(5,5) 의 거리가 같아야하며, 모든 사과가 있는 칸을 지나야함.

(간단한 풀이)
(1,1)에서 (y,x)까지 갈 수 있는 모든 경우의 수가 정답.

 

#include <cstdio>
int ans,K,a[6][6],dy[4]={-1,1,0,0},dx[4]={0,0,1,-1};
int sol2(int y,int x,int c,int t){
    if(y==5&&x==5) return c==t && c+t==24-K;
    int ret =0;
    for(int i=0;i<4;i++){
        int ny=y+dy[i],nx=x+dx[i];
        if(ny<1||nx<1||ny>5||nx>5||a[ny][nx]) continue;
        a[ny][nx]=1;
        ret+=sol2(ny,nx,c+1,t);
        a[ny][nx]=0;
    }
    return ret;
}
void sol(int y,int x,int c){
    int v = sol2(y,x,0,c);
    ans+=v;
    for(int i=0;i<4;i++){
        int ny=y+dy[i],nx=x+dx[i];
        if(ny<1||nx<1||ny>5||nx>5||a[ny][nx]) continue;
        a[ny][nx]=1;
        sol(ny,nx,c+1);
        a[ny][nx]=0;
    }
}
int main(){
    scanf("%d",&K);
    for(int i=0;i<K;i++){
        int y,x;
        scanf("%d%d",&y,&x);
        a[y][x]=1;
    }
    a[1][1]=1;
    sol(1,1,0);
    printf("%d",ans);
}

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