[BAE/<JOON> 문제풀이] 19236. 청소년 상어

 

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

19236번: 청소년 상어

서론

구현 문제. 고려해야할 인자들이 많아서 상당히 헷갈린다. 나도 여러 인자들이 꼬여있는 로직에서 틀린걸 못찾아서 3시간을 헤맸다.

---

풀이

그냥 문제에 있는걸 그대로 코드로 옮기면 된다. 그래서 풀이를 쓸 게 없다.

개인적으로 느낀 점은 알고리즘 문제 풀 때 본인만의 코딩 규칙을 만들고 지키는게 상당히 중요할 것 같다.

이 문제에서 좌표를 나타내는 구조체에는 x, y로 선언을 해놓고 상어를 움직일 때 y, x로 해서 틀렸다.

평소 2차원 좌표 문제를 풀 때 수학적으로는 맞지 않지만 알파벳 순으로 [x][y] 할 때도 있고 수학적으로 고려해서 [y][x] 식으로 할 때도 있다보니 이런 복잡한 문제에서 틀리는 것 같다. 앞으로 [y][x]로 고정해야겠다.

---

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <cstdlib>
using namespace std;
const long long mod = 10e8 + 7;
using ll = long long;
struct fi {
	int i, d, die = 0;
};
struct co {
	int x, y;
};
int mvx[8] = { 0, -1, -1, -1, 0, 1, 1, 1 };
int mvy[8] = { -1 ,-1, 0, 1, 1, 1, 0, -1 }; 
int n = 4;
int r(co sp, vector<vector<fi>> arr, vector<co> pos) {
	arr[sp.y][sp.x].die = 1;	
	int shd = arr[sp.y][sp.x].d - 1;
	for (int i = 1; i <= n * n; i++) {
		co cp = pos[i];		
		if (arr[cp.y][cp.x].die == 1) continue;
		int d = arr[cp.y][cp.x].d - 1;
		for (int k = 0; k < 8; k++) {
			int mx = cp.x + mvx[(d + k) % 8];
			int my = cp.y + mvy[(d + k) % 8];
			if (mx > n || my > n || mx < 1 || my < 1 || (mx == sp.x && my == sp.y)) continue;
			arr[cp.y][cp.x].d = (d + k) % 8 + 1;
			co t = pos[arr[cp.y][cp.x].i]; pos[arr[cp.y][cp.x].i] = pos[arr[my][mx].i]; pos[arr[my][mx].i] = t;
			fi tmp = arr[cp.y][cp.x]; arr[cp.y][cp.x] = arr[my][mx]; arr[my][mx] = tmp;
			break;
		}
	} 
	
	/*for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (arr[i][j].die == 1) {
				cout << 0 << " ";
			}
			else {
				cout << arr[i][j].i << " ";
			}
		}
		cout << "\t";
		for (int j = 1; j <= n; j++) {
			cout << arr[i][j].d << " ";
		}
		cout << "\n";
	}
	cout << "\n";*/
	int sd = 1;
	int mx = 0;
	while (sp.y + mvy[shd] * sd >= 1 && sp.x + mvx[shd] * sd >= 1 && sp.y + mvy[shd] * sd <= n && sp.x + mvx[shd] * sd <= n) {
		int ny = sp.y + mvy[shd] * sd;
		int nx = sp.x + mvx[shd] * sd;	
		if (arr[ny][nx].die == 0) {
			int s1 = r({ nx, ny }, arr, pos);
			mx = mx > s1 ? mx : s1;
		}
		sd++;
	}
	return mx + arr[sp.y][sp.x].i;
}
int main()
{
	ios::sync_with_stdio(0); cin.tie(0);
	vector<vector<fi>> arr(n + 1, vector<fi>(n + 1)); vector<co> pos(n * n + 1);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> arr[i][j].i >> arr[i][j].d;
			pos[arr[i][j].i] = { j, i };
		}
	}	

	/*for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cout << arr[i][j].i << " ";
		}
		cout << "\t";
		for (int j = 1; j <= n; j++) {
			cout << arr[i][j].d << " ";
		}
		cout << "\n";
	}
	cout << "\n";*/

	cout << r({ 1, 1 }, arr, pos);
	return 0;
}