글 읽기 - 메모리 초과 질문드립니다!

gloom1 4년 전 0

테케는 모두 정답으로 나오지만 제출시 메모리 초과가 나옵니다...

BFS 쪽에 문제가 있는 것인지, 변수를 비효율적으로 잡고 있는 것인지 잘 모르겠습니다.

조언 부탁드리겠습니다 ㅜㅜ

/*
	<sol>
	우선 각 집으로부터 치킨집까지 최단거리를 구하는 함수가 필요하다. => BFS
	이렇게 최단거리를 구한 뒤 sum으로 도시의 치킨거리를 구한다.
	도시의 치킨거리를 min으로 update 시킨다.

	폐업할 치킨집을 고르는 알고리즘이 필요하다.
	Brute force로 하자.
	치킨집의 pos를 모두 vector에 저장해둔다.
	별도로 perm vector를 만들어서 next_permutation()으로 순회하며
	1이 나온 치킨집은 살리고 나머지는 폐업한다.
	고를 수 있는 치킨집의 개수는 M부터 최소 1까지 고르도록 하자.
 */

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <cstring>

#define vec vector
using namespace std;

const int INF = 987654321;
const int EMPTY = 0;
const int HOUSE = 1;
const int CHICKEN = 2;
const int VALID_CHICKEN = 3;
const int MAX_SIZE = 50;

int city[MAX_SIZE + 1][MAX_SIZE + 1];
bool visited[MAX_SIZE + 1][MAX_SIZE + 1];
int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { -1, 1, 0, 0 };
int size, maxChickenLeft;
int answer = INF;

vec<int> invalidPos = { -1, -1 };

int getManhattanDistance(vec<int> & from, vec<int> & to) {
	return abs(from[0] - to[0]) + abs(from[1] - to[1]);
}

bool isInRange(int y, int x) {
	return (y > 0) && (y <= ::size) && (x > 0) && (x <= ::size);
}

// BFS
vec<int> getNearestChicken(vec<int> & housePos) {
	vec<int> nearestChicken;
	memset(visited, false, sizeof(visited));
	queue<vec<int>> bfsQueue;
	bfsQueue.push(housePos);

	while (!bfsQueue.empty()) {
		int curY = bfsQueue.front()[0], curX = bfsQueue.front()[1];
		visited[curY][curX] = true;
		bfsQueue.pop();

		for (int i = 0; i < 4; i++) {
			int newY = curY + dy[i], newX = curX + dx[i];
			if (!isInRange(newY, newX)) continue;
			if (visited[newY][newX]) continue;
			if (city[newY][newX] == VALID_CHICKEN) {
				return { newY, newX };
			}
			bfsQueue.push({ newY, newX });
		}
	}

	return invalidPos;
}


int main() {
	cin >> ::size >> ::maxChickenLeft;
	vec<vec<int>> chickenPos, housePos;
	for (int y = 1; y <= ::size; y++) {
		for (int x = 1; x <= ::size; x++) {
			cin >> city[y][x];
			if (city[y][x] == CHICKEN) chickenPos.push_back({ y, x });
			if (city[y][x] == HOUSE) housePos.push_back({ y, x });
		}
	}

	int numChicken = chickenPos.size();
	vec<int> perm(numChicken, 0);

	for (int i = ::maxChickenLeft; i > 0; i--) {
		fill(perm.begin(), perm.end(), 0);
		fill(perm.end() - i, perm.end(), 1);
		do {
			// Use Back tracking
			for (int j = 0; j < numChicken; j++) {
				int y = chickenPos[j][0], x = chickenPos[j][1];
				if (perm[j] == 1 && city[y][x] == CHICKEN) {
					city[y][x] = VALID_CHICKEN;
				}
			}
			// 이제 유효한 치킨집 다 고름
			// 이 치킨 집들에 대해서 bfs 해야 함.
			int cityChickenDist = 0;
			for (auto house : housePos) {
				vec<int> nearestChicken = getNearestChicken(house);
				cityChickenDist += getManhattanDistance(house, nearestChicken);
            }
			::answer = min(::answer, cityChickenDist);

			// undo
			for (int j = 0; j < numChicken; j++) {
				int y = chickenPos[j][0], x = chickenPos[j][1];
				if (perm[j] == 1 && city[y][x] == VALID_CHICKEN) {
					city[y][x] = CHICKEN;
				}
			}
		} while (next_permutation(perm.begin(), perm.end()));

	}

	cout << ::answer << "\n";

	return 0;
}

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

문제

문제

출처

ICPC

메모리 초과 질문드립니다!

gloom1 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말