[코드트리] 병원 거리 최소화하기 (삼성 SW 역량테스트 2018 상반기 오후 2번)

 

A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기)

 

삼성 A형 전체 링크

 

https://www.codetree.ai/training-field/frequent-problems/problems/min-of-hospital-distance

이후 설명 및 입/출력은 링크 참고

 

병원 거리 최소화하기 문제 풀이는 BOJ 15686 : 치킨 배달과 같다.

#include <stdio.h>

#define MAX (50 + 10)

int T;
int N, M;
int MAP[MAX][MAX];
int hospitalList[MAX * 2];

typedef struct st
{
	int r;
	int c;
}RC;

RC person[MAX * 2];
RC hospital[13 + 5];
int pcnt, hcnt;

int minAnswer;

int abs(int a, int b)
{
	return (a > b) ? a - b : b - a;
}

int getLength(int x1, int y1, int x2, int y2)
{
	return abs(x1, x2) + abs(y1, y2);
}

int minValue(int a, int b)
{
	return (a < b) ? a : b;
}

void input()
{
	scanf("%d %d", &N, &M);

	pcnt = hcnt = 0;

	for (int r = 0; r < N; r++)
	{
		for (int c = 0; c < N; c++)
		{
			scanf("%d", &MAP[r][c]);

			if (MAP[r][c] == 1)
			{
				person[pcnt].r = r;
				person[pcnt++].c = c;
			}
			else if (MAP[r][c] == 2)
			{
				hospital[hcnt].r = r;
				hospital[hcnt++].c = c;
			}
		}
	}
}

int calculate()
{
	int sum, tmp, min;

	sum = 0;
	for (int i = 0; i < pcnt; i++)
	{
		tmp = 0;
		min = 0x7fff0000;
		for (int k = 0; k < hcnt; k++)
		{
			if (hospitalList[k + 1] == 0) continue;
			min = minValue(min, getLength(person[i].r, person[i].c, hospital[k].r, hospital[k].c));
		}

		sum += min;
	}

	return sum;
}

void DFS(int L, int hospitalCount)
{
	if (hospitalCount > M) return;

	if (L > hcnt) /* 치킨집 보다 많으면 종료 */
	{
		if (hospitalCount == M) /* 선택된 치킨집이 M과 같을 때만 계산 */
		{
			int tmp = calculate();
			if (tmp < minAnswer) minAnswer = tmp;
		}

		return;
	}

	hospitalList[L] = 1;
	DFS(L + 1, hospitalCount + 1);

	hospitalList[L] = 0;
	DFS(L + 1, hospitalCount);
}

int main(void)
{
	// scanf("%d", &T);
	T = 1;
	for (int tc = 1; tc <= T; tc++)
	{
		input();
		minAnswer = 0x7fff0000;

		DFS(1, 0);

		printf("%d\n", minAnswer);
	}

	return 0;
}