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

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

19236번: 청소년 상어

문제

아기 상어가 성장해 청소년 상어가 되었다.

4×4크기의 공간이 있고, 크기가 1×1인 정사각형 칸으로 나누어져 있다. 공간의 각 칸은 (x, y)와 같이 표현하며, x는 행의 번호, y는 열의 번호이다. 한 칸에는 물고기가 한 마리 존재한다. 각 물고기는 번호와 방향을 가지고 있다. 번호는 1보다 크거나 같고, 16보다 작거나 같은 자연수이며, 두 물고기가 같은 번호를 갖는 경우는 없다. 방향은 8가지 방향(상하좌우, 대각선) 중 하나이다.

오늘은 청소년 상어가 이 공간에 들어가 물고기를 먹으려고 한다. 청소년 상어는 (0, 0)에 있는 물고기를 먹고, (0, 0)에 들어가게 된다. 상어의 방향은 (0, 0)에 있던 물고기의 방향과 같다. 이후 물고기가 이동한다.

물고기는 번호가 작은 물고기부터 순서대로 이동한다. 물고기는 한 칸을 이동할 수 있고, 이동할 수 있는 칸은 빈 칸과 다른 물고기가 있는 칸, 이동할 수 없는 칸은 상어가 있거나, 공간의 경계를 넘는 칸이다. 각 물고기는 방향이 이동할 수 있는 칸을 향할 때까지 방향을 45도 반시계 회전시킨다. 만약, 이동할 수 있는 칸이 없으면 이동을 하지 않는다. 그 외의 경우에는 그 칸으로 이동을 한다. 물고기가 다른 물고기가 있는 칸으로 이동할 때는 서로의 위치를 바꾸는 방식으로 이동한다.

물고기의 이동이 모두 끝나면 상어가 이동한다. 상어는 방향에 있는 칸으로 이동할 수 있는데, 한 번에 여러 개의 칸을 이동할 수 있다. 상어가 물고기가 있는 칸으로 이동했다면, 그 칸에 있는 물고기를 먹고, 그 물고기의 방향을 가지게 된다. 이동하는 중에 지나가는 칸에 있는 물고기는 먹지 않는다. 물고기가 없는 칸으로는 이동할 수 없다. 상어가 이동할 수 있는 칸이 없으면 공간에서 벗어나 집으로 간다. 상어가 이동한 후에는 다시 물고기가 이동하며, 이후 이 과정이 계속해서 반복된다.

<그림 1>

<그림 1>은 청소년 상어가 공간에 들어가기 전 초기 상태이다. 상어가 공간에 들어가면 (0, 0)에 있는 7번 물고기를 먹고, 상어의 방향은 ↘이 된다. <그림 2>는 상어가 들어간 직후의 상태를 나타낸다.

<그림 2>

이제 물고기가 이동해야 한다. 1번 물고기의 방향은 ↗이다. ↗ 방향에는 칸이 있고, 15번 물고기가 들어있다. 물고기가 있는 칸으로 이동할 때는 그 칸에 있는 물고기와 위치를 서로 바꿔야 한다. 따라서, 1번 물고기가 이동을 마치면 <그림 3>과 같아진다.

<그림 3>

2번 물고기의 방향은 ←인데, 그 방향에는 상어가 있으니 이동할 수 없다. 방향을 45도 반시계 회전을 하면 ↙가 되고, 이 칸에는 3번 물고기가 있다. 물고기가 있는 칸이니 서로 위치를 바꾸고, <그림 4>와 같아지게 된다.

<그림 4>

3번 물고기의 방향은 ↑이고, 존재하지 않는 칸이다. 45도 반시계 회전을 한 방향 ↖도 존재하지 않으니, 다시 회전을 한다. ← 방향에는 상어가 있으니 또 회전을 해야 한다. ↙ 방향에는 2번 물고기가 있으니 서로의 위치를 교환하면 된다. 이런 식으로 모든 물고기가 이동하면 <그림 5>와 같아진다.

<그림 5>

물고기가 모두 이동했으니 이제 상어가 이동할 순서이다. 상어의 방향은 ↘이고, 이동할 수 있는 칸은 12번 물고기가 있는 칸, 15번 물고기가 있는 칸, 8번 물고기가 있는 칸 중에 하나이다. 만약, 8번 물고기가 있는 칸으로 이동하면, <그림 6>과 같아지게 된다.

<그림 6>

상어가 먹을 수 있는 물고기 번호의 합의 최댓값을 구해보자.

입력

첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 8보다 작거나 같은 자연수를 의미하고, 1부터 순서대로 ↑, ↖, ←, ↙, ↓, ↘, →, ↗ 를 의미한다.

출력

상어가 먹을 수 있는 물고기 번호의 합의 최댓값을 출력한다.

 

시물레이션 문제인데, 나는 어렵게 오래걸려서 해결했다 심지어 내 힘으로 해결하지 못하고

질문검색에 올려서 해결했다, 내 힘으로 고칠 수 있었던 것 같은데 한 번 더 해볼걸

 

어쨋든, 나는 이 문제에서 가장 까다로웠던 부분이 물고기를 이동시키고 난 후 그 map에서 상어가 이동할 수 없다면 다시 전 상태로 돌려놓는 것이 가장 까다로웠다. 이 부분은 재귀함수로 해결하고자 했고, 3차원 배열을 통해 각 물고기가 이동한 횟수상태에 따라 그 상태를 저장해주었다.

adj[depth][i][j] -> 물고기를 depth번 이동 시켰을 때 i,j에 위치한 물고기

와 같은 형식으로 나타내주었다. 

 

그리고 물고기의 위치는 배열을 하나 선언해서 물고기 번호에 해당하는 인덱스에 위치를 저장하는 식으로 바로 물고기 위치를 알 수 있도록 저장해주었다.

 

 

< 문제 해결 >

1. 주어진 선제조건 -> 상어는 (0,0) 물고기를 먹고 그 방향성을 가진다. (0,0)에 있던 물고기는 시작과 동시에 먹히므로 존재하지 않는걸로 보아도 무방하다. (이 부분은 입력 함수에 같이 두었다)

2. 이제 "물고기 이동 -> 상어 이동"을 상어가 갈 곳이 없어질 때까지 구현해주어야하는데 이 부분을 백트래킹으로 구현 해주었다.

상어 이동이 가능하면 재귀함수로 depth가 하나씩 증가하게 되고 이동가능한 위치에 상어를 옮겨준다. 그리고 물고기를 이동시킨 후 그 상태를 저장해준다. 다시 상어 이동이 가능한지 확인하고, 가능하다면 똑같이 재귀함수로 반복해주고, 이동이 불가능하다면 return으로 돌아온다. 다시 돌아오면 전에 저장해주었던 depth에 맞는 맵으로 되돌려주고 상어가 다른 위치로 이동 가능한지 확인해주면서 반복한다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <cmath>
#define INF 9876543210
#define ENDL cout << endl;
#define endl '\n'
#define swap(type, x, y) do{type t=y;y=x;x=t;}while(0)
using namespace std;

typedef long long ll;
typedef pair<int, int> pl;

// BOJ :: https://www.acmicpc.net/problem/19236
// 맵에 저장할 정보 1. 물고기가 존재하는지, 2. 물고기 번호, 3. 물고기의 방향성
struct infor {
	bool isFish;
	int Number;
	int Direct;
};

struct d {
	int y;
	int x;
};

struct position {
	int y, x;
	bool islive;
};

infor adj[4][4], copy_adj[50][4][4];
bool Die[17];
const d Dir[9] = { {0,0}, {-1,0}, {-1,-1}, {0,-1}, {1,-1}, {1,0}, {1,1}, {0,1}, {-1,1} };
position pos[17];

// 벡터에 상어 정보를 담는다
vector<pair<int, pair<int, int>>> v;
int Answer, Sum;

void Copy(int depth) {
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			copy_adj[depth][i][j] = adj[i][j];
		}
	}
}

void Reverse(int depth) {
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			adj[i][j] = copy_adj[depth][i][j];
		}
	}
}

void Reverse_Pos(int depth) {
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			pos[copy_adj[depth][i][j].Number].y = i;
			pos[copy_adj[depth][i][j].Number].x = j;
		}
	}
}

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

void Input() {
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			int Num, Dir;
			cin >> Num >> Dir;
			adj[i][j].isFish = true;
			adj[i][j].Number = Num;
			adj[i][j].Direct = Dir;

			pos[Num].y = i;
			pos[Num].x = j;
			pos[Num].islive = true;
		}
	}

	// 초기에 상어가 (0,0) 물고기를 먹고 그 방향을 가지는 사실은 변하지 않는다.
	v.push_back({ adj[0][0].Direct, {0,0} });
	Die[adj[0][0].Number] = true;
	pos[adj[0][0].Number].islive = false;
	adj[0][0].isFish = false;

	Sum = adj[0][0].Number;
}

bool isCan_SharkMove() {
	int y = v.back().second.first;
	int x = v.back().second.second;
	int dir = v.back().first;

	for (int i = 1; i <= 3; i++) {
		int ny = y + (Dir[dir].y * i);
		int nx = x + (Dir[dir].x * i);

		if (isValid(ny, nx) && adj[ny][nx].isFish) {
			return true;
		}
	}
	return false;
}

void Fish_Move() {
	int shark_y = v.back().second.first;
	int shark_x = v.back().second.second;
	for (int i = 1; i <= 16; i++) {
		// 상어한테 먹혀 존재하지 않는 물고기는 건너띄어줍니다
		if (Die[i] == true) continue;
		// 물고기 번호에 저장해놓은 좌표로 방향과 위치를 불러옵니다
		int y = pos[i].y;
		int x = pos[i].x;
		int d = adj[y][x].Direct;
		int count = 8;
		while (count--) {
			int ny = y + Dir[d].y;
			int nx = x + Dir[d].x;

			// 해당 범위 밖이거나
			if (!isValid(ny, nx)) {
				d++;
				if (d == 9) d = 1;
				continue;
			}
			// 해당 범위 안이지만 그 위치에 상어가 존재하는 경우에 방향을 돌려줍니다
			else if (shark_y == ny && shark_x == nx) {
				d++;
				if (d == 9) d = 1;
				continue;
			}
			// 모두 해당 되지 않으면 그 위치에 있는 물고기와 위치를 바꿔줍니다
			else {
				adj[y][x].Direct = d;
				int Temp_y = pos[i].y, Temp_x = pos[i].x;
				pos[i].y = pos[adj[ny][nx].Number].y;
				pos[i].x = pos[adj[ny][nx].Number].x;

				pos[adj[ny][nx].Number].y = Temp_y;
				pos[adj[ny][nx].Number].x = Temp_x;
				swap(infor, adj[y][x], adj[ny][nx]);

				break;
			}
		}
	}
}


void func(int depth, int total) {
	// 물고기 이동
	Fish_Move();

	// 상어가 이동할 수 있는 다음 위치들에 물고기가 존재하는지 확인
	if (!isCan_SharkMove()) {
		Answer = max(Answer, total);
		return;
	}
	// 물고기가 이동한 형태의 맵을 저장해준다
	Copy(depth);

	int y = v.back().second.first;
	int x = v.back().second.second;
	int dir = v.back().first;
	for (int i = 1; i <= 3; i++) {
		int ny = y + (Dir[dir].y * i);
		int nx = x + (Dir[dir].x * i);

		if (isValid(ny, nx) && adj[ny][nx].isFish) {
			v.push_back({ adj[ny][nx].Direct, {ny, nx} });
			adj[ny][nx].isFish = false;
			Die[adj[ny][nx].Number] = true;
			pos[adj[ny][nx].Number].islive = false;
			total += adj[ny][nx].Number;

			func(depth + 1, total);

			// 맵을 전 상태로 돌려놓습니다
			Reverse(depth);
			// 물고기 위치를 전 상태로 돌려놓습니다
			Reverse_Pos(depth);

			v.pop_back();
			adj[ny][nx].isFish = true;
			Die[adj[ny][nx].Number] = false;
			pos[adj[ny][nx].Number].islive = true;
			total -= adj[ny][nx].Number;
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	Input();
	func(0, Sum);
	cout << Answer << endl;

	return 0;
}

나는 처음에 

상어가 이동 가능한 구역이 있는지 확인 -> 물고기 이동

으로 구현해주었는데, 문제 지문에 나와있듯이

물고기 이동 -> 상어가 이동 가능한 구역이 있는지 확인

을 해주어야한다. 저 순서 때문에 2일 동안 문제점을 못찾고 있었다.

 

문제를 똑바로 읽고, 틀리면 문제부터 다시 읽어보자.