어떤 자료구조를 써야 좋을까요. 정비소 문제랑 상당히 비슷합니다. 관리해야 하는 변수가 많이 있습니다. 여기서 어떻게 분리해서 사용가능할까요? 먼저 벡터를 쓸지 큐를 쓸지 결정을 하고, 하나에 대해서 정독을 해서 따라가보도록 하겠습니다. 그런데, ㅋ큐의 경우에는 포문을 사용해서 돌릴 수가 없고, 단순하게 제일 앞에 있는 것만 가져와서 사용하고 지우기가 가능합니다. 지우고 채우고를 반복하는 것이기 때문에 큐가 좋을지는 아직 불확실합니다. 어떤 알고리즘이 괜찮을지 한번 생각해보도록 하겠습니다. |
/* 사람 번호를 가지고 가겠습니다. 1,2,3, 4,5,6 사람 번호와 위치를 먼저 t 에 넣겠습니다. 그리고 t2 에는 모두 나왔을 때를 넣겠습니다. 구조체를 사용해서 변수 관리만 잘해주면 되겠습니다. */ #include <iostream> #include <queue> #include <algorithm> #include <vector> using namespace std; #define SIZE 7 // 11; int map[SIZE][SIZE]; int a; int b; int x, y, nx, ny; int N, n; int ans; int person_cnt; int visit[11]; int minute; int index; struct person { int n, x, y, w; }; queue<person> stair_1, stair_2; vector<person> t1, t2; struct stair_pos{ int x, y, t; }; stair_pos arr[2]; void problemIn() { cin >> N; int a; for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) { cin >> map[i][j]; if (map[i][j] == 1) { t1.push_back({ n++,i,j }); person_cnt++; } else { arr[a].x = i; arr[a].y = j; arr[a].t = map[i][j]; a++; } } } } void visit_init() { for (int i = 0; i < person_cnt; i++) { visit[i] = 0; } } /* 일단 나누는 것부터 해야합니다. 6명의 사람이 있을 때, 000000 6자리의 자릿수가 있을 때, 이것을 0아니면 1로 넣는 경우의 수는 2^6 = 64의 경우의 수 입니다. 000000 ~ 111111 12 는 8 + 4 -> 일단 64개의 경우의 수를 만들도록 하겠습니다. 사람1, 사람2, 사람3 이 일단 1번 계단으로 간다 이것입니다. */ void make_binary(int x, int up) { for (int i = 0; x > 0; i++) { visit[up - 1] = x % 2; x /= 2; up--; } } /* 스테어로 가기 까지 걸리는 시간에 대해서 계산을 해서 넣습니다. 넣어준 다음에, 시간을 경과 시킵니다. */ void go_stair() { for (int i = 0; i < stair_1.size(); i++) { stair_1[i].t }
minute++; } void solve() { for (int i = 0; i < pow(2, person_cnt); i++) { // i = 7; 로 넣으면 visit 가 0 0 0 1 1 1 이렇게 나옵니다. 그럼 0 인 것은 1번 계단 1 인 것은 2번 계단으로 이동하겠습니다. make_binary(i, person_cnt); index = 0; for (int j = 0; j < person_cnt; j++) { if (visit[j] == 0) { stair_1.push({ t1[index].n, t1[index].x, t1[index].y, abs(t1[index].x - arr[0].x) + abs(t1[index].y - arr[0].y)}); index++; } else { stair_2.push({ t1[index].n, t1[index].x, t1[index].y, abs(t1[index].x - arr[1].x) + abs(t1[index].y - arr[1].y) }); index++; } } go_stair(); /* 여기서 6개의 사람에 대해서 000 001 이렇게 나뉘어집니다. 오께이. 그럼 여기서 알고리즘 들어감 */ visit_init(); } } int main() { int T; cin >> T; for (int tc = 1; tc <= T; tc++) { problemIn(); solve(); cout << "#" << tc << " " << ans << endl; ans = 0; } return 0; }
|