글 읽기 - 전역배열로 초기화 및 복원하면 답이 다르게 나오는 이유가 뭔가요??

piano9637 3년 전 0

dfs함수안에다가 info fishes_temp 와 int arr_temp를 선언하고 저장 및 초기화를 해주면 AC가 나옵니다.

이유가 뭔가요??

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

struct info {
	int y, x;
	int dir;
	bool alive = false;
};
int result = 0;
int arr[4][4] = { 0, };
int y_arr[9] = { 0,-1,-1,0,1,1,1,0,-1 };
int x_arr[9] = { 0,0,-1,-1,-1,0,1,1,1 };
info fishes[17];
int arr_temp[4][4]; 
info fishes_temp[17];
void save(void)
{
	for (int i = 0; i < 4; i++)
	{
		for (int j = 0; j < 4; j++)
		{
			arr_temp[i][j] = arr[i][j];
		}
	}
	for (int i = 1; i <= 16; i++)
	{
		fishes_temp[i] = fishes[i];
	}
}

void init(void)
{
for (int i = 0; i < 4; i++)
	{
		for (int j = 0; j < 4; j++)
		{
			arr[i][j] = arr_temp[i][j];
		}
	}
	for (int i = 1; i <= 16; i++)
	{
		fishes[i] = fishes_temp[i];
	}
}
void move_fish(int shark_y, int shark_x)
{
	// 번호가 작은 물고기들 부터
	for (int i = 1; i <= 16; i++)
	{
		if (fishes[i].alive == false) continue;
		int y = fishes[i].y; int x = fishes[i].x;
		int dir = fishes[i].dir; int num = i;
		bool flag = false;
		// 해당 물고기의 현재 방향 이 가능한지 체크
		int y_move = y + y_arr[dir]; int x_move = x + x_arr[dir];
		if (y_move >= 0 && y_move < 4 && x_move >= 0 && x_move < 4)
		{
			if (y_move != shark_y || x_move != shark_x)
			{
				if (arr[y_move][x_move] == 0) // 빈자리 일때
				{
					arr[y_move][x_move] = num;
					arr[y][x] = 0;
					fishes[num].y = y_move; fishes[num].x = x_move;
					flag = true;
 				}
				else // 다른 물고기가 있을때
				{
					fishes[num].y = y_move; fishes[num].x = x_move;
					fishes[arr[y_move][x_move]].y = y; fishes[arr[y_move][x_move]].x = x;
					arr[y][x] = arr[y_move][x_move];
					arr[y_move][x_move] = num;
					flag = true;
				}
			}
		}
		if (flag == true) continue;
		// 다른 7방향
		int ndir = dir + 1;
		if (ndir == 9) ndir = 1;
		while (ndir != dir)
		{
			int y_move = y + y_arr[ndir]; int x_move = x + x_arr[ndir];
			fishes[num].dir = ndir;
			if (y_move >= 0 && y_move < 4 && x_move >= 0 && x_move < 4)
			{
				if (y_move != shark_y || x_move != shark_x)
				{
					if (arr[y_move][x_move] == 0) // 빈자리
					{
						arr[y_move][x_move] = arr[y][x];
						arr[y][x] = 0;
						fishes[num].y = y_move; fishes[num].x = x_move;
						fishes[num].dir = ndir;
						break;
					}
					else // 다른 물고기
					{
						fishes[num].y = y_move; fishes[num].x = x_move; fishes[num].dir = ndir;
						fishes[arr[y_move][x_move]].y = y; fishes[arr[y_move][x_move]].x = x;
						arr[y][x] = arr[y_move][x_move];
						arr[y_move][x_move] = num;
						break;
					}
				}
			}
			ndir++;
			if (ndir == 9) ndir = 1;
		}
	}
	return;
}
void dfs(int shark_y, int shark_x, int shark_dir, int sumnum)
{
	save();
	result = max(result, sumnum);
	// 물고기 이동
	move_fish(shark_y, shark_x);
	// 상어이동
	int y = shark_y; int x = shark_x;
	for (int i = 1; i <= 3; i++)
	{
		int y_move = y + y_arr[shark_dir] * i; int x_move = x + x_arr[shark_dir] * i;
		if (y_move < 0 || y_move > 3 || x_move < 0 || x_move > 3)
		{
			break;
		}
		if (arr[y_move][x_move] != 0)
		{
			int num = arr[y_move][x_move];
			int dir = fishes[num].dir;
			// 물고기를 죽이고
			fishes[num].alive = false;
			arr[y_move][x_move] = 0;
			// 상어 이동
			dfs(y_move, x_move, dir, sumnum + num);
			// 물고기 복원
			fishes[num].alive = true;
			arr[y_move][x_move] = num;
		}
	}
	init();
	return;
}
int main(void)
{
	int a, b = 0;
	int shark_num, shark_dir = 0;
	for (int i = 0; i < 4; i++)
	{
		for (int j = 0; j < 4; j++)
		{
			cin >> a >> b;
			if (i == 0 && j == 0)
			{
				shark_num = a;
				shark_dir = b;
			}
			else
			{
				arr[i][j] = a;
				fishes[a] = { i,j,b,true };
			}
		}
	}
	dfs(0, 0, shark_dir, shark_num);
	cout << result;
}

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

문제

문제

출처

ICPC

전역배열로 초기화 및 복원하면 답이 다르게 나오는 이유가 뭔가요??

piano9637 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말