백준 c++ 19236 "청소년 상어" -PlusUltraCode-

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

 

 

 

 

 

 

 

이 코드는 주어진 4x4 격자에서 물고기들을 먹으면서 최종 점수를 최대로 만드는 문제를 해결하는 코드입니다. 각 물고기는 고유의 번호와 이동 방향을 가지고 있으며, 상어가 이 물고기들을 먹으며 이동할 때 가능한 최대 점수를 계산합니다.

주요 변수와 함수 설명

1. 전역 변수
   • vector<vector<Node>> cArr: 격자의 상태를 저장하는 2차원 벡터. 각 원소는 (물고기 번호, 방향) 쌍을 나타냅니다.
   • int resultMax: 상어가 얻을 수 있는 최대 점수를 저장.
   • int Result: 현재 상어가 얻은 점수.
   • int fishCount: 현재 남아 있는 물고기 수.
   • vector<bool> visited: 물고기의 방문 여부를 확인하는 벡터.
2. 함수
   • void Input(): 입력을 받아 격자 상태를 초기화.
   • bool isInside(int sero, int garo): 주어진 좌표가 격자 내에 있는지 확인.
   • bool findDir(int nowSero, int nowGaro): 현재 위치의 물고기가 이동할 수 있는 방향을 찾고, 이동 가능한 경우 방향을 변경.
   • void swap(int nowSero, int nowGaro): 현재 물고기와 이동할 위치의 물고기를 교환.
   • int eatFish(int nowSero, int nowGaro): 현재 위치의 물고기를 먹고 점수를 추가.
   • Node findMinFish(): 현재 방문하지 않은 물고기 중 가장 작은 번호를 가진 물고기의 위치를 찾음.
   • void fishRotation(): 모든 물고기를 번호 순서대로 이동.
   • void DFS(int nowSero, int nowGaro): 깊이 우선 탐색을 사용하여 가능한 모든 경로를 탐색하고, 최대 점수를 계산.
   • void Print(): 격자의 상태를 출력(디버깅용).

코드 풀이 과정

1. 입력 받기
   • Input() 함수에서 4x4 격자의 상태를 입력받아 초기화합니다.
2. 초기 설정
   • 상어가 첫 번째 물고기를 먹습니다(eatFish(0, 0)).
   • 물고기 수를 1 감소시킵니다.
3. DFS 호출
   • 상어가 (0, 0)에서부터 DFS를 시작합니다(DFS(0, 0)).
4. DFS 함수
   • 현재 위치의 물고기의 방향을 가져옵니다.
   • 물고기들을 이동시킵니다(fishRotation()).
   • 상어가 이동할 수 있는 모든 방향에 대해 재귀적으로 탐색합니다.
   • 상어가 이동할 때마다 현재 상태를 저장하고, 점수를 갱신하며, 이동 후 원래 상태로 되돌리는 백트래킹을 수행합니다.
5. 결과 출력
   • 상어가 얻을 수 있는 최대 점수를 출력합니다.

핵심 로직

• 물고기 이동: 모든 물고기는 번호 순서대로 이동하며, 이동 가능한 방향을 찾습니다.
• 상어 이동: 상어는 현재 위치에서 물고기의 방향으로 1~3칸 이동할 수 있으며, 이동 가능한 모든 경우를 재귀적으로 탐색합니다.
• 백트래킹: 상어의 모든 이동을 시도해보고, 점수가 더 높은 경우를 찾아내어 최대 점수를 갱신합니다.

이 과정을 통해 상어가 얻을 수 있는 최대 점수를 계산합니다.

 

 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
typedef pair<int, int> Node;
int dy[8] = { -1,-1,0,1,1,1,0,-1 };
int dx[8] = { 0,-1,-1,-1,0,1,1,1 };

int resultMax = -1;

vector<vector<Node>> cArr;
int Result = 0;
int fishCount = 16;


void Input() {

	cArr.resize(4);
	for (int i = 0; i < 4; i++) {
		cArr[i].resize(4);
	}

	for (int i = 0; i < 4; i++) {
		for (int k = 0; k < 4; k++) {
			int num;
			int dir;
			cin >> num >> dir;
			cArr[i][k] = { num,dir-1 };
		}
	}
	
}

bool isInside(int sero, int garo) {
	if (sero >= 0 && sero < 4 && garo >= 0 && garo < 4) {
		return true;
	}
	return false;
}


bool findDir(int nowSero, int nowGaro ) {

	int nowDirection = cArr[nowSero][nowGaro].second;
	int nextDirection = nowDirection;
	int flag = 0;

	while (1) {
		int nextSero = nowSero + dy[nextDirection];
		int nextGaro = nowGaro + dx[nextDirection];
		if (isInside(nextSero,nextGaro) == false || cArr[nextSero][nextGaro].first == 0) {
			nextDirection = (nextDirection + 1) % 8;
			if (nextDirection == nowDirection)break;
		}
		else {
			flag = 1;
			break;
		}
	}

	if (flag == 1) {
		cArr[nowSero][nowGaro].second = nextDirection;
		return true;
	}
	else {
		return false;
	}

}
void swap(int nowSero, int nowGaro) {
	int direction = cArr[nowSero][nowGaro].second;

	int nextSero = nowSero + dy[direction];
	int nextGaro = nowGaro + dx[direction];

	Node temp = { cArr[nextSero][nextGaro].first,cArr[nextSero][nextGaro].second };
	cArr[nextSero][nextGaro] = cArr[nowSero][nowGaro];
	cArr[nowSero][nowGaro].first = temp.first;
	cArr[nowSero][nowGaro].second = temp.second;
}

int eatFish(int nowSero, int nowGaro) {
	int backResult = cArr[nowSero][nowGaro].first;

	Result += cArr[nowSero][nowGaro].first;
	cArr[nowSero][nowGaro].first = 0;

	if (Result > resultMax)resultMax = Result;

	return backResult;
}

vector<bool> visited;

Node findMinFish() {
	
	int minNumber = 999;
	Node index = { -1,-1 };

	for (int i = 0; i < 4; i++) {
		for (int k = 0; k < 4; k++) {
			if (cArr[i][k].first <= 0)continue;
			if (visited[cArr[i][k].first] == false)continue;
			if (cArr[i][k].first < minNumber) {
				
				minNumber = cArr[i][k].first;
				
				index = { i,k };
			}
		}
	}

	if(minNumber!=999)visited[minNumber] = false;

	return index;

}

void fishRotation() {
	visited.clear();
	visited.resize(17,true);

	for (int i = 0; i < fishCount; i++) {
		Node index = findMinFish();
		int nowSero = index.first;
		int nowGaro = index.second;
		if (findDir(nowSero, nowGaro) == true) {
			swap(nowSero, nowGaro);
		}
		
	}

}

void DFS(int nowSero,int nowGaro) {
	vector<vector<Node>> copyArr;
	
	int direction = cArr[nowSero][nowGaro].second;
	fishRotation();
	for (int i = 1; i <= 3; i++) {
		int nextSero = nowSero + dy[direction]*i;
		int nextGaro = nowGaro + dx[direction] * i;

		if (isInside(nextSero, nextGaro) == false)continue;
		if (cArr[nextSero][nextGaro].first == -1)continue;
		copyArr = cArr;
		cArr[nowSero][nowGaro].first = -1;
		fishCount--;
		int backResult =eatFish(nextSero, nextGaro);
		DFS(nextSero, nextGaro);
		Result -= backResult;
		fishCount++;
		cArr = copyArr;
	}
	
}


void Print() {
	for (int i = 0; i < 4; i++) {
		for (int k = 0; k < 4; k++) {
			cout << cArr[i][k].first << " " << cArr[i][k].second << " ";
		}
		cout << '\n';
	}
}

int main(void) {
	Input();
	int no = eatFish(0, 0);
	fishCount--;
	DFS(0, 0);
	cout << resultMax;
	

}