백준 15898번 피아의 아틀리에 ~신비한 대회의 연금술사~

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

15898번: 피아의 아틀리에 ~신비한 대회의 연금술사~

 

 

 

 

 

<접근방법>

처음에는 dfs0 기저에서 dfs1 호출, dfs1 기저에서 dfs2 호출, dfs2 기저에서 계산...

이렇게 하려고 했습니다.

그런데 가마상태 관리를 어떻게 해야할지 도저히 모르겠어서 다른 분의 코드를 참고하였습니다.

하나의 dfs로 3개의 다른 상태에 대한 완전탐색을 합니다.

이때 가마의 현재 상태를 매개변수로 넘기면서 가마의 상태를 관리합니다.

가마는 구조체 2차원 배열입니다.

이걸 매개변수로 넘기는게 꽤 복잡합니다.

그래서 2차원 벡터에 가마를 저장합니다.

 

 

 

---

 

 

 

<코드>

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

const int INF = 987654321;
struct state {
	int x;
	char c;
};

int n, res = -INF;
int visited[10];

state material[10][4][4][4];
vector<vector<state> > map(5, vector<state>(5));

int cal(vector<vector<state>> tmap) {
	int r = 0, b = 0, g = 0, y=0;

	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 5; j++) {
			char t = tmap[i][j].c;

			if (t == 'R') {
				r += tmap[i][j].x;
			}
			else if (t == 'B') {
				b += tmap[i][j].x;
			}
			else if (t == 'G') {
				g += tmap[i][j].x;
			}
			else if (t == 'Y') {
				y += tmap[i][j].x;
			}
		}
	}

	return 7 * r + 5 * b + 3 * g + 2 * y;
}

vector<vector<state>> take_material(vector<vector<state>> tmap, int seq ,int pos, int dir) {
	//material[seq][dir][i][j]
	int px, py;

	switch (pos) {
	case 0:
		px = 0; py = 0;
		break;
	case 1:
		px = 1; py = 0;
		break;
	case 2:
		px = 0; py = 1;
		break;
	case 3:
		px = 1; py = 1;
		break;
	default:
		break;
	}

	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			int y = i + py, x = j + px;
			tmap[y][x].x += material[seq][dir][i][j].x;

			if (tmap[y][x].x > 9) {
				tmap[y][x].x = 9;
			}
			else if (tmap[y][x].x < 0) {
				tmap[y][x].x = 0;
			}


			if (material[seq][dir][i][j].c != 'W') {
				tmap[y][x].c = material[seq][dir][i][j].c;
			}
		}
	}

	return tmap;
}

void dfs(int dep, vector<vector<state>> v) {
	if (dep == 3) {
		res = max(cal(v), res);
		return;
	}

	//순서, 위치, 방향을 정해야한다.
	//순서
	for (int i = 0; i < n; i++) {
		if (visited[i] == 1) continue;
		visited[i] = 1;

		//위치
		for (int j = 0; j < 4; j++) {
			//방향
			for (int k = 0; k < 4; k++) {
				vector<vector<state>> tmp = take_material(v, i, j, k);

				dfs(dep+1, tmp);
			}
		}

		visited[i] = 0;
	}
}

void make_rotated() {
	for (int z = 0; z < n; z++) {
		for (int r = 1; r < 4; r++) {
			for (int i = 0; i < 4; i++) {
				for (int j = 0; j < 4; j++) {
					material[z][r][i][j].x = material[z][r - 1][3 - j][i].x;
					material[z][r][i][j].c = material[z][r - 1][3 - j][i].c;
				}
			}
		}
	}
}

int main() {
	cin >> n;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 4; j++) {
			for (int k = 0; k < 4; k++) {
				int t;
				cin >> material[i][0][j][k].x;
			}
		}

		for (int j = 0; j < 4; j++) {
			for (int k = 0; k < 4; k++) {
				cin >> material[i][0][j][k].c;
			}
		}
	}

	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 5; j++) {
			map[i][j].x = 0;
			map[i][j].c = 'W';
		}
	}

	make_rotated();

	dfs(0, map);

	cout << res << '\n';

	return 0;
}

 

 

 

---

 

 

 

<느낀 점>

-여러 상태에 대한 완전탐색은 이렇게 하면 되는구나!

-switch문 사용법에 대해 배웠다. break빼먹으면 답 이상하게 나온다!

-벡터의 생성자

vector의 생성자는 첫 인자로 배열의 사이즈, 두 번째로 초기값을 쓴다.

vector<int> arr(5, 0)는 5의 크기, 0의 초기값을 의미하겠다.

이차원 배열의 경우, vector<vector<int>> arr(5, vector<int>(5, 0)) 이렇게 사용하면 되겠다.