청소년 상어/ 백트래킹

www.acmicpc.net/problem/19236

19236번: 청소년 상어

#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<deque>
#include<math.h>
#include<cmath>
#include<unordered_map>

using namespace std;

int dx[] = {0,-1,-1,0,1,1,1,0,-1};
int dy[] = {0,0,-1,-1,-1,0,1,1,1};

int n = 4;
int maxnum = 0;

struct fish {
	
	int num;
	int way;
};


vector<vector<fish>>arr(4, vector<fish>(4));

fish nothing = { 0,0 };

bool canGo(int x, int y)
{
	return x >= 0 && y >= 0 && x < n && y < n && arr[x][y].num != 17;
}

bool sharkCanGo(int x, int y) {

	return x >= 0 && y >= 0 && x < n && y < n ;

}

void print() {
	
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++)
		{
			
			cout <<"("<< arr[i][j].num<<","<<arr[i][j].way<<")"<<" ";
			
		}

		cout << endl;
	}
	cout << endl;

}


void fishMove(fish& f, int x, int y, map<int, pair<int, int>>&fishloc) {

	int way = f.way;
	int nx = x + dx[way];
	int ny = y + dy[way];

	int count = 1;

	while (!canGo(nx, ny)) {
		
		if (count == 8) { return; }
		way = (way + 1) % 8;
		if (way == 0) { way = 8; }
		nx = x + dx[way];
		ny = y + dy[way];
		count++;
	
	}


	if (arr[nx][ny].num != 0) { //만약에 빈칸이 아닌 물고기가 있는 경우
		pair<int, int>temp;
		temp = fishloc[arr[nx][ny].num];
		fishloc[arr[nx][ny].num] = fishloc[arr[x][y].num]; // 두 물고기의 정보를 저장
		fishloc[arr[x][y].num] = temp;
	}
	else {  //빈칸인 경우
		fishloc[arr[x][y].num] = make_pair(nx, ny);  // 옮길 물고기의 정보만 저장
	}
	arr[x][y].way = way;
	swap(arr[x][y], arr[nx][ny]);

}

void sharkMove(map<int,pair<int, int >> &fishloc, int nx, int ny) {

	int x = fishloc[17].first;
	int y = fishloc[17].second;

	swap(arr[x][y], arr[nx][ny]); // 상어와 물고기 바꾸기

	arr[nx][ny].way = arr[x][y].way;  // 원래있던 물고기의 방향으로 변경
	fishloc[17] = make_pair(nx, ny);  // 
	
	fishloc.erase(arr[x][y].num);  //기존의 물고기 없애기
	arr[x][y] = nothing;

}


void simulate(fish & shark, map<int, pair<int, int>>&fishloc) {
	
	map<int, pair<int, int>>::iterator it;

	for (it = fishloc.begin(); it != fishloc.end(); it++) {
		
		if (it->first != 17) {

			fishMove(arr[it->second.first][it->second.second], it->second.first, it->second.second, fishloc);

		}
	}


}


void dfs(fish & shark, map<int, pair<int, int>>&fishloc,int fishEat) {
	
	simulate(shark, fishloc); //시뮬레이션 먼저 한다.
	
	int way = shark.way;
	int nx = fishloc[17].first+dx[way];
	int ny = fishloc[17].second+dy[way];

	fish originShark = shark;
	map<int, pair<int, int>> originfishloc = fishloc;
	vector<vector<fish>>originarr = arr;

	while (1) {
		if (sharkCanGo(nx, ny)) { //상어가 갈 수 있는 영역 인지 판단
			if (arr[nx][ny].num != 0) { 

				int fnum = arr[nx][ny].num;   //이동하는 곳의 물고기 번호

				shark.way = arr[nx][ny].way;  //물고기의 방향과 동일하게 변경


				sharkMove(fishloc, nx, ny); // 상어 움직이기

				dfs(shark, fishloc, fishEat + fnum);

				//상태 복원
				arr = originarr;
				shark = originShark;
				fishloc = originfishloc;

			}

			nx = nx + dx[way];
			ny = ny + dy[way];
		}
		else {
			break; //더이상 갈 수 없으면 while문 빠져나옴.
		}

	}

	if (!sharkCanGo(nx, ny)) {  //기저조건 ** 기저조건을 함수의 마지막 부분에 배치해야하는 것 주의 ** 

		if (maxnum < fishEat) { 
			maxnum = fishEat;
		}

		return;
	}


}






int main() {

	map<int,pair<int, int>>fishloc;
	
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			
			int a,b;
			cin >> a >> b;
			fish f = { a,b };
			fishloc[a] = make_pair(i, j);
			arr[i][j] = f;
		
		}
	}

	int fnum = arr[0][0].num;

	fish shark = { 17,arr[0][0].way };
	fishloc.erase(arr[0][0].num);
	fishloc[17] = make_pair(0, 0);
	arr[0][0] = shark;
	
	dfs(shark, fishloc, fnum); 
	cout << maxnum<<endl;

}

- 보통 재귀함수에서 기저조건을 앞에 다 두는데 그렇게 하다가 계속 틀려서 기저조건을 함수의 마지막에 두었더니 잘 되었다. 

- 시뮬레이션 -> 조건 검사(while 문, 재귀) -> 조건 불만족 시 while 문 빠져나오고 리턴