[백준][C++] 19236: 청소년 상어

문제 링크: https://www.acmicpc.net/problem/19236

 

올해 상반기 코테 기출이라고 합니다. 이런 문제는 읽기도 싫게 생겼습니다 끙;

 

그냥 적당히 써있는대로 풀면 됩니다. 45도씩 반시계로 회전하는건 적당히 d=(d+1)%8 이런식으로 하심 됩니다.

문제가 상어가 여러군데로 갈 수 있는 경우인데, 재귀함수로 백트래킹하거나, 상태공간 struct랑 큐를 만들어서 BFS를 돌려줘야 합니다. 어느 루트를 타야 먹은 애들의 합이 최대가 될 지 모르니까요. 결국은 모든 경우의 수를 다 해봐야 합니다.

 

8퀸 문제같은 경우 상태공간을 압축을 해줘야되는데(2차원 체스판 --> 1차원배열 --> 비트마스킹으로 8bit integer에 저장 등) 이 문제는 뭐 그럴 필요가 없습니다.

#include <bits/stdc++.h>
using namespace std;


// 윗쪽 방향부터 반시계로 45도씩
const int dy[] = { -1, -1, 0, 1, 1, 1, 0, -1 };
const int dx[] = { 0, -1, -1, -1, 0, 1, 1, 1 };

// 이게 d=(d+1)%8보다 더 빠름
constexpr int turn(int d) {
	return (d == 7 ? 0 : d + 1);
}

constexpr bool in_range(int y, int x) {
	return y >= 0 && y < 4 && x >= 0 && x < 4;
}


struct status {
	tuple<int, int, int> shark;		// y, x, dir
	pair<int, int> fish[4][4];	// index[1, 16], direction[0, 7], idx==0 -> 빈칸
	int remain;					// 남은 물고기
	int eaten;					// 먹은 물고기 번호 합

	// 상어를 [y][x]로 이동
	// ([y][x]에 물고기 있다고 가정)
	void move_shark(int _y, int _x) {
		auto& [y, x, d] = shark;
		auto& [f_idx, f_dir] = fish[_y][_x];

		assert(f_idx != 0);

		y = _y, x = _x;
		d = f_dir;

		--remain;
		eaten += f_idx;
		f_idx = 0;
	}

	// 모든 물고기 이동
	void move_fish() {
		for (int idx = 1; idx <= 16; ++idx) {
			bool found = false;
			const auto& [s_y, s_x, s_dir] = shark;

			for (int i = 0; i < 4 && !found; ++i) {
				for (int j = 0; j < 4 && !found; ++j) {
					auto& [f_idx, f_dir] = fish[i][j];
					if (f_idx != idx) continue;

					// 45도씩 돌려보기
					for (int cnt = 0; cnt < 8; ++cnt) {
						auto next_y = i + dy[f_dir];
						auto next_x = j + dx[f_dir];
						if (!in_range(next_y, next_x) || (s_y == next_y && s_x == next_x)) {
							f_dir = turn(f_dir);
							continue;
						}

						swap(fish[i][j], fish[next_y][next_x]);
						found = true;
						break;
					}
				}
			}
		} // for idx
	}
};



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

	status input;
	for (int i = 0; i < 4; ++i) {
		for (int j = 0; j < 4; ++j) {
			int idx, dir;
			cin >> idx >> dir;
			--dir;
			input.fish[i][j] = { idx, dir };
		}
	}
	input.remain = 16;
	input.eaten = 0;


	// [0, 0] 물고기 먹기
	input.move_shark(0, 0);


	int mx = input.eaten;
	queue<status> q;
	q.push(input);

	while (!q.empty()) {
		auto current = q.front();
		q.pop();

		mx = max(mx, current.eaten);
		current.move_fish();

		auto [y, x, d] = current.shark;
		auto next_y = y + dy[d];
		auto next_x = x + dx[d];

		while (in_range(next_y, next_x)) {
			if (current.fish[next_y][next_x].first == 0) {
				next_y += dy[d];
				next_x += dx[d];
				continue;
			}

			auto next_status = current;
			next_status.move_shark(next_y, next_x);

			if (next_status.remain)
				q.push(next_status);

			next_y += dy[d];
			next_x += dx[d];
		}
	}

	cout << mx << '\n';

	return 0;
}

참고로 d=(d+1)%8보다 if else가 더 빠릅니다

근데 이 문제는 뭐 무한루프만 안나오면 어떻게 풀든 시간초과 날 일은 없습니다.