[Algorithm] 홈 방범 서비스 (SW Expert Academy – 2217)

by

문제 출처

  • https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V61LqAf8DFAWu

난이도

  • 하 – 중 – (상) – 최상 – 풀지 못함

문제 (항상 대략적인 설명만 작성합니다. 문제는 위 출처에서 확인하세요)

  • N x N Matrix 크기로 생긴 도시에 집들이 있다. 주어진 도시 정보에서 집을 최대한 많이 커버하는 마름모 크기를 찾는 게 문제이다. 마름모 크기가 커질수록 지출이 커지고, 마름모 안에 집이 들어가면 수입이 생겨서 지출이 줄어든다. 총지출이 마이너스가 되지 않으면서 최대한 많은 집을 커버하는 마름모를 찾으면 된다. SW Expert Academy의 경우 문제 공개를 하면 안 된다고 되어있어서 더 상세히 문제를 작성하지 않았다. 상세한 내용은 위 사이트에서 확인 부탁합니다.

후기

  • 개인적으로 정말 어려운 문제였다고 생각한다. 내 방식대로 문제를 풀고 나서 다른 사람들의 답을 확인해보니 본 문제는 Manhattan 거리를 계산하는 문제였다. 이 부분을 알고 다시 문제를 풀어보니 정말로 쉽게 해결되었다. 그래서 이번에는 총 2가지 답안을 정리하였다.
  • 우선 처음에는 Recursive 함수를 만들어서 모든 방법을 찾아보려고 했다. 하지만, 사방으로 퍼져나가는 마름모를 정확하게 구현하지 못하여서 계속 에러가 났다. 사방으로 퍼져나가는 경우 Recursive 함수를 사용하면 한번 방문했던 곳을 여러 번 반복해서 방문하거나, 한쪽으로만 계속 퍼져나갔다가 다른 방향으로 가기 때문에 만약 매트릭스의 값을 변경해야 하거나 하는 경우 정확한 계산을 하지 못하였다. 그래서 시도한 방법이 Stack을 사용하여 모든 방법을 검색하는 것을 구현하였다. Stack의 크기가 4, 8, 12, 16으로 증가해가면 마름모의 크기가 하나씩 증가한 것을 확인하여 총 집의 개수, 수입, 지출을 계산하였다.
  • 마지막으로 다른 사람들의 답안을 보고 Manhattan 거리 측정하여 문제를 풀어보았다. 아래 그림은 마름모의 크기를 Manhattan 거리 계산 방법을 사용한 예를 보여준다. 숫자 0을 기준으로 하면 1로 표시된 부분은 기준점으로부터 Manhattan 거리 1만큼 떨어진 곳이다. 2의 경우 기준으로부터 Manhattan 거리가 2 떨어진 부분이다. 이렇게 계산을 하면 정말 쉽게 문제를 해결 할 수 있었다.

그림 1: Manhattan 거리 계산 방법을 사용하여 마름모 크기 계산

코드

  • Stack을 사용하여 문제를 해결한 코드 (완전 비효율 적임)
#include <stdio.h>

//MK: Visual Studio를 사용시 scanf 에러 제거함.
#pragma warning(disable:4996)

#define MAXSIZE 61
#define STACKMAX 367

#define MAX(a,b) (a)>(b)?(a):(b)
#define ND(a) (a+20)

int direction[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };

int inputList[MAXSIZE][MAXSIZE];
int maxIncome[MAXSIZE][MAXSIZE];
int visitedMap[MAXSIZE][MAXSIZE];
int inputSize;
int income;

int stack1[STACKMAX][2];
int fPtr1;
int ePtr1;
int stackSize1;

//MK: Stack Insert/Pop을 위한 코드
void insertIntoStack1(int y, int x) {
	stack1[ePtr1][0] = y;
	stack1[ePtr1][1] = x;
	ePtr1++;
	if (ePtr1 >= STACKMAX) {
		ePtr1 = 0;
	}
	stackSize1++;
}

void popFromStack1(int *y, int *x) {
	*y = stack1[fPtr1][0];
	*x = stack1[fPtr1][1];
	fPtr1++;
	if (fPtr1 >= STACKMAX) {
		fPtr1 = 0;
	}
	stackSize1--;
}

void init() {
	for (int i = 0; i < MAXSIZE; i++) {
		for (int j = 0; j < MAXSIZE; j++) {
			visitedMap[i][j] = 0;
		}
	}
}

//MK: Stack을 사용한 문제 해결 코드
int findMax(int y, int x, int id) {
	fPtr1 = 0;
	ePtr1 = 0;
	stackSize1 = 0;
	insertIntoStack1(y, x);
	int numHouse = inputList[y][x];
	int finalRet = 0;
	int tmp = (numHouse *income) - 1;
	if(tmp >= 0){
		finalRet = numHouse;
	}
	visitedMap[y][x] = id;
	int maxRun = (inputSize+1) * 4;
	int nextStackSize = 4;
	int needToRun = 1;
	while (1) {
		if(needToRun == 0){
			if (maxRun == nextStackSize) {
				break;
			}
			int size = (nextStackSize / 4) + 1;
			nextStackSize += 4;
			int tmp = (numHouse *income) - ((size)*(size)+(size - 1)*(size - 1));
			if (tmp >= 0) {
				finalRet = numHouse;
			}
			needToRun = stackSize1;
		}
		int yPtr, xPtr;
		popFromStack1(&yPtr, &xPtr);
		for (int i = 0; i < 4; i++) {
			int nextY = yPtr + direction[i][0];
			int nextX = xPtr + direction[i][1];
			if (visitedMap[nextY][nextX] != id) {
				visitedMap[nextY][nextX] = id;
				insertIntoStack1(nextY, nextX);
				numHouse += inputList[nextY][nextX];
			}
		}
		needToRun--;
	}
	return finalRet;
}

void findAllIncome() {
	init();
	int id = 1;
	for (int i = 0; i < inputSize; i++) {
		for (int j = 0; j < inputSize; j++) {
			maxIncome[i][j] = findMax(ND(i), ND(j), id);
			id++;
		}
	}
}

int findMaxValue() {
	int ret = 0;
	for (int i = 0; i < inputSize; i++) {
		for (int j = 0; j < inputSize; j++) {
			ret = MAX(ret, maxIncome[i][j]);
		}
	}
	return ret;
}

int main(void)
{
	int testCase;
	freopen("input.txt", "r", stdin);
	setbuf(stdout, NULL);
	scanf("%d", &testCase);
	for (int m = 1; m <= testCase; m++)
	{
		//init();
		scanf("%d %d", &inputSize, &income);
		for (int i = 0; i < inputSize; i++) {
			for (int j = 0; j < inputSize; j++) {
				scanf("%d", &inputList[ND(i)][ND(j)]);
			}
		}
		findAllIncome();
		printf("#%d %d\n", m, findMaxValue());
	}
	return 0;
}
  • Manhattan 거리 계산 방법을 사용한 코드
#include <stdio.h>

//MK: Visual Studio를 사용시 scanf 에러 제거함.
#pragma warning(disable: 4996) 

//#define DEBUG

#define MAXSIZE 20
#define MAXDIS 41
#define MAX(a, b) (a)>(b)?(a):(b)

int ABS(int a) {
	if (a < 0) {
		return a * -1;
	}
	return a;
}

int inputList[MAXSIZE][MAXSIZE];
int maxHouse[MAXSIZE][MAXSIZE];
int numHouse[MAXDIS];
int inputSize;
int income;
int answer;

//MK: 현재 X, Y를 기준으로 각 거리의 집 개수 계산하는 부분
int findNumHouse(int y, int x) {
	for (int i = 0; i <= (inputSize * 2); i++) {
		numHouse[i] = 0;
	}
	for (int i = 0; i < inputSize; i++) {
		for (int j = 0; j < inputSize; j++) {
			int dis = ABS(y - i) + ABS(x - j);
			numHouse[dis] += inputList[i][j];
		}
	}
	int tmp = 0;
	for (int i = 0; i <= (inputSize * 2); i++) {
		int cost = (i + 1) * (i + 1) + (i*i);
		tmp += numHouse[i];
		if ((tmp * income) >= cost) {
			maxHouse[y][x] = tmp;
			answer = MAX(answer, tmp);
		}
#ifdef DEBUG
		printf("%d - %d\n", i, numHouse[i]);
#endif
	}

}

int main() {
	freopen("input.txt", "r", stdin);
	int testCase = 0;
	scanf("%d", &testCase);
	for (int m = 1; m <= testCase; m++) {
		answer = 0;
		scanf("%d %d", &inputSize, &income);
		for (int i = 0; i < inputSize; i++) {
			for (int j = 0; j < inputSize; j++) {
				scanf("%d", &inputList[i][j]);
			}
		}
		for (int i = 0; i < inputSize; i++) {
			for (int j = 0; j < inputSize; j++) {
				findNumHouse(i, j);
			}
		}
		printf("#%d %d\n", m, answer);
	}
	return 0;
}

추가 출처

  1. http://bbs.nicklib.com/algorithm/1697

Leave a Comment