글 읽기 - 2일째 붙들고 있습니다. 도움 부탁드려요

rlawnddnjs12 2년 전 0

2일 동안 붙들고 있는 문제인데 해결이 안되네요,, 다른 분들 코드를 참고해서 해결할 수 있지만,

제가 생각해서 작성한 코드로 꼭 맞추고 싶어서 질문드립니다..

다른 부분보다 물고기를 이동 시키고 상어가 이동할 수 없다면 다시 전으로 돌아가 물고기를 전 위치, 방향으로 복구시켜야하는 부분이

이 문제에서 가장 까다로운 부분이라고 생각 됩니다.

저는 물고기의 이동횟수에 따라 그 상태의 맵을 3차원 배열에 저장해주었습니다. 가장 맨처음에 상어가 (0,0)으로 들어가는 것은 변하지 않으므로

가장 처음 물고기가 이동한 맵을 copy_adj[0][i][j]에 저장해주고 상어가 먹을 수 있는 곳이 존재한다면 백트래킹 기법으로 depth가 증가하면서 그 depth에 맞게 adj[depth][i][j]에 저장을 해주었습니다. 그리고 depth+1에서 상어가 먹을 수 있는 곳이 존재하지 않으면 return으로 다시 돌아가 전에 저장해주었던

adj[depth][i][j]맵으로 되돌려주었습니다.

물고기의 위치도 똑같이 깊이를 이용해서 변경해주고, 되돌리고 그런 방식으로 구현했습니다.

문제의 예제, 질문검색에 올려주신 예제는 모두 맞게 나옵니다 ㅜ

코드가 많이 길고 난잡하지만 도움 부탁드려요 ㅜㅜ

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

	int y = v.back().second.first;
	int x = v.back().second.second;
	int dir = v.back().first;
	bool isCan = false;
	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) {
			isCan = true;
			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;
		}
	}
	if (!isCan) {
		Answer = max(Answer, total);
	}
}

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

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

	return 0;
}

zigui 2년 전 1

163번 줄 if문이 물고기를 이동시킨 뒤에 실행되어야 합니다.

rlawnddnjs12 2년 전 0

감사합니다 ! 덕분에 해결할 수 있었습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

2일째 붙들고 있습니다. 도움 부탁드려요

rlawnddnjs12 2년 전 0

zigui 2년 전 1

rlawnddnjs12 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말