BOJ 01857 : 발레리노

이 문제는 Flood fill 문제를 살짝 응용해서 풀 수 있는 문제이다.

4 5
1 0 0 0 0
3 0 0 0 0
0 0 2 0 0
0 0 0 4 0
우선 위의 예제 입력을 보면 0은 맨땅 1은 방석이 있는곳 2는 돌멩이가 있는 위치, 3은 김주성이 춤을 시작하는 위치이다. 우리는 김주성이 춤을 마치는 위치인 4번으로 가야하며 김주성은 방석이 깔린 곳으로만 이동한다 (김주성은 체스에서의 나이트와 동일하게 움직인다)

그럼 우리는 시작하는 위치에서 Flood fill(우리의 필요에 맞춰 변형되었는)을 이용해서 김주성이 갈 수있는 위치를 파악 할 수 있다.

이러한 이동 경로를 보면 3에서 4로 갈 때 필요한 방석의 수는

위의 그림과 같이 2개가 필요한 최소 방석 수 이며 이제 방석을 놓을 수 있는 가짓수를 구해보도록 하자

이렇게 가짓수 또한 3가지 라는 것을 알 수 있다.

하지만 이를 할 때 해당 알고리즘을 3번돌리게 되면 시간 초과가 되는 것이 다반사이며 필자도 처음에 문제를 풀 때 시간 복잡도를 고려하지 않았다가 시간 초과를 내었었다.
이를 해결하기 위해서는 Flood Fill 알고리즘을 중복적으로 돌리지 않는 것이 중요하다.

간단한 내용이지만 간과했을 시 BFS 알고리즘을 다루는 과정에서 실수를 하기 쉬우니 유의하길 바란다.

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
vector<pair<int, int> >ipg[33][33];
queue<pair<int, int> > ipq;
int n,m,ivs[33][33],ipf[33][33],ipd[33][33],imr[9][3]={{2,-1},{2,1},{-2,-1},{-2,1},{1,-2},{-1,-2},{-1,2},{1,2}},ans=-999;
long long ips[33][33];
void regg(int st,int ed,int psx, int psy)
{
	int i,ntx,nty;
	ivs[psx][psy]=1;
	if(ipf[psx][psy]==2)return;
	if(ipf[psx][psy]!=1&&(!(psx==st&&psy==ed)))
    {
    	ipg[st][ed].push_back({psx,psy});
        return;
    }
	for(i=0;i<8;i++) {
		ntx=psx+imr[i][0],nty=psy+imr[i][1];
		if(ntx<0||nty<0||ntx>=n||nty>=m||ivs[ntx][nty]==1)continue;
		regg(st,ed,ntx,nty);
	}
	return;
}
int main()
{
	int nx,ny,i,j,k,stx,sty,x,y,edx,edy;
	scanf("%d %d",&n,&m);
	for(i=0;i<n;i++)
	{
		for(j=0;j<m;j++)
		{
			scanf("%d",&ipf[i][j]);
			if(ipf[i][j]==3)stx=i,sty=j;
			if(ipf[i][j]==4)edx=i,edy=j;
		}
	}
	for(i=0;i<n;i++)
    {
		for(j=0;j<m;j++)
        {
			fill(&ivs[0][0],&ivs[31][31],0),regg(i,j,i,j);
        }
    }
	ipq.push({stx,sty});
    ipd[stx][sty]=1;
    ips[stx][sty]=1;
	while(!ipq.empty())
	{
		x=ipq.front().first;
        y=ipq.front().second;
        ipq.pop();
		for(i=0;i<ipg[x][y].size();i++)
		{
			nx=ipg[x][y][i].first;
            ny=ipg[x][y][i].second;
			if(ipd[nx][ny]==0)
            	ipd[nx][ny]=ipd[x][y]+1,ips[nx][ny]=ips[x][y],ipq.push({nx,ny});
			else if(ipd[nx][ny]==ipd[x][y]+1)
            	ips[nx][ny]+=ips[x][y];
		}
	}
	if(!ipd[edx][edy])printf("-1\n");
 	else printf("%d\n%lld\n",ipd[edx][edy]-2,ips[edx][edy]);
	return 0;
}