[백준 17406] 배열돌리기 4

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

17406번: 배열 돌리기 4

요구 사항

1. 회전 연산의 순서 정하기

2. 회전 시키기

3. 값 구하기

 

1번 풀이

- play[] 배열을 선언하여 dfs을 이용하여 순서를 정하였다.

- visit 배열로 방문했는지 안했는지 체크하였다.

- dfs(now, num)으로 dfs을 이용하였다.

- num은 현재 위치를 나타내고, 방문하지 않았다면 i번째 순서로 정한다 라는 로직으로 구성

 

2번 풀이

여러가지 풀이가 있겠으나 나는 끝에서 끝까지 간다음 범위를 벗어나면 방향을 바꾸고 

시작 위치에 도달하면 종료로 구성하였다.

한칸 씩 이동해야 하므로 temp변수로 현재값과 다음값을 저장하여 한칸씩 이동하였다.

1. 시작 위치 정하기

2. temp에 현재 값과 다음 값을 저장

3. 초기 방향 값

4. 방향 값 함수 구현 void getdir(int d)

5. 범위 넘어가면 방향 바꾸기, 초기 위치로 돌아왔는지 확인, 값 변경 및 초기화

 

3번 풀이

3번은 각 행의 최대 값을 구하면 된다

최대값이 답이 된다.

 

소스코드

#include <iostream>
#include <queue>
#include <vector>
#include <string.h>
using namespace std;
struct go{
	int r;
	int c;
	int num;
};
int map[51][51];
int n,m,k;
int play[7];
int visit[7];
vector<go> magic;
int dr[4] ={-1,0,1,0};
int dc[4] = {0,-1,0,1};
int ans=987654321;
void show(int data[][51])
{
	cout<<"S"<<endl;
	for(int i=0 ; i < n ; i++)
	{
		for(int j=0 ; j < m ; j++)
		{
			cout<<map[i][j]<<" ";
		}
		cout<<endl;
	}
}
int getdir(int d)
{
	if(d==3)
		return d=2;
	else if(d==2)
	return d=1;
	else if(d==1)
	return d=0;
	else if(d==0)
	return d=1;
}
void rotate(int sr, int sc, int num)
{
	for(int i=num; i>=1 ; i--)
	{
		int ssr = sr + i*dr[0];
		int ssc = sc + i*dc[1];
		int rr,cc;
		int dir=3;
		int nexttemp=map[ssr][ssc];
		int nowtemp=map[ssr][ssc];
		rr= ssr;
		cc =ssc;
		int cnt=0;
		while(true)
		{
			cnt++;
			nexttemp=nowtemp;
			int nr = rr +dr[dir];
			int nc = cc +dc[dir];
	//		cout<<"nr"<<nr<<"nc"<<nc<<endl;
			if(nr==ssr && nc==ssc)
			{
	//			cout<<"ASDF"<<endl;
				map[nr][nc]=nexttemp;
				break;
			}
			if( nr <ssr || nc <ssc || nr >ssr+i*2 || nc >ssc +i*2)
			{
	//			cout<<"AA"<<endl;
				dir=getdir(dir);
				continue;
			}
			nowtemp=map[nr][nc];
			map[nr][nc]=nexttemp;
			rr=nr;
			cc=nc;
		}
	}
}
void dfs(int now,int num)
{
	if(num==k)
	{
		int mapc[51][51];
		memcpy(mapc,map,sizeof(map));
		for(int i=1 ; i<=num ; i++)
		{
			int r = magic.at(play[i]-1).r;
			int c = magic.at(play[i]-1).c;
			int nu = magic.at(play[i]-1).num;
	//		cout<<"nu"<<nu<<endl;
			rotate(r,c,nu);
		}
		for(int i=0 ; i < n ; i++)
		{
			int sum=0;
			for(int j =0 ; j<m ; j++)
			{
				sum+=map[i][j];
		}
			if(ans>sum)
			{
				ans=sum;
			}
			
		}
		memcpy(map,mapc,sizeof(map));
		return;
	}
	if(num==k || num>k)
		return;
	for(int i=1;i<=k;i++)
	{
		if(visit[i]==1)
			continue;
		play[num+1]=i;
		visit[i]=1;
		dfs(i,num+1);
		visit[i]=0;
	}
}
int main()
{
	scanf("%d%d%d",&n,&m,&k);
	for(int i=0 ; i < n ; i++)
	{
		for(int j=0;j<m;j++)
		{
			scanf("%d",&map[i][j]);
		}
	}
	for(int i=0 ; i < k ; i++)
	{
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		magic.push_back({x-1,y-1,z});
	}
	for(int i=1 ; i <=k ; i++)
	{
		memset(visit,0,sizeof(visit));
		memset(play,0,sizeof(play));
		visit[i]=1;
		play[1]=i;
		dfs(i,1);
	}
	
	cout<<ans<<endl;
}