[백준] 19236 청소년 상어💫

백준 19236 청소년 상어

• https://www.acmicpc.net/problem/19236

• 어디가 틀렸을까...

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int dirr[8] = { -1, -1, 0, 1, 1, 1, 0, -1 };
int dirc[8] = {0, -1, -1, -1, 0, 1, 1, 1 };


//상어가 (r,c)에 있을 때 앞으로 먹을 수 있는 물고기의 합의 최댓값
int moveShark(int r, int c, vector<pair<int, int>> mp[]) {

	//(r,c)좌표의 물고기를 먹는다
	int ret = mp[r][c].first;

	//(r,c)좌표에 상어가 있다
	mp[r][c].first = -1;
	
	//물고기 이동
	//작은 번호의 물고기부터 하나씩 이동
	for (int fish = 1; fish <= 16; fish++) {
		for(int i = 0; i < 4; ++i)
			for (int j = 0; j < 4; ++j) {
				if (mp[i][j].first == fish) {

					int fishdir = mp[i][j].second;

					for (int k = 0; k < 8; ++k) {
						int nextr = i + dirr[fishdir];
						int nextc = j + dirc[fishdir];

						//이동할 수 없는 경우 반시계방향 45도 회전
						if (nextr < 0 || nextr >= 4 || nextc < 0 || nextc >= 4 || mp[nextr][nextc].first == -1) {
							fishdir++;
							if (fishdir == 8) fishdir = 0;
							continue;
						}

						//이동할 수 있는 경우 swap
						mp[i][j].first = mp[nextr][nextc].first;
						mp[i][j].second = mp[nextr][nextc].second;
						mp[nextr][nextc].first = fish;
						mp[nextr][nextc].second = fishdir;
						break;
					}
				}
			}
	}

	//상어 이동
	//(r,c)는 빈칸이 된다
	mp[r][c].first = 0;
	//상어의 방향 = 먹은 물고기의 방향
	int sharkdir = mp[r][c].second;
	
	//상어가 앞으로 먹게 되는 물고기 번호의 합
	int sum = 0;

	while (true) {
		int nextr = r + dirr[sharkdir];
		int nextc = c + dirc[sharkdir];

		//이동 범위를 넘어선 경우
		if (nextr < 0 || nextr >= 4 || nextc < 0 || nextc >= 4)
			break;
	
		//이동 범위 안에 있는 경우
		//빈 칸이 아니면 이동할 수 있다
		if(mp[nextr][nextc].first != 0) 
			sum = max(sum, moveShark(nextr, nextc, mp));

		//한 칸 이상 이동할 수 있음
		r = nextr;
		c = nextc;
	}

	return ret + sum;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	//first: 빈칸 0, 상어 -1, 물고기 1 ~ 16
	//second: 방향
	vector<pair<int, int>> mp[4];

	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			int a, b;
			cin >> a >> b;
			//방향 0~7 되도록 1 빼준다
			mp[i].push_back(make_pair(a, b-1));
		}
	}

	cout << moveShark(0, 0, mp);
	return 0;
}