BOJ 15686 : 치킨 배달 (삼성 SW TEST A형)

삼성 A형 전체 링크

 

www.acmicpc.net/workbook/view/1152 (A형 문제집)

 

www.acmicpc.net/problem/15686

 

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

 

input을 받을 때, 치킨집과 집의 좌표를 받아두자.

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

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

			if (MAP[r][c] == 1)
			{
				house[hcnt].r = r;
				house[hcnt++].c = c;
			}
			else if (MAP[r][c] == 2)
			{
				chicken[ccnt].r = r;
				chicken[ccnt++].c = c;
			}
		}
	}
}

 

이제 선택할 치킨집 리스트를 만들어야 한다.

살아남는 치킨집 리스트를 만들고, 그 치킨집에 대해 최소값을 갱신하면 된다.

DFS를 이용해서 만들어보자.

void DFS(int L, int chickenCount)
{
	if (chickenCount > M) return;
    
	if (L > ccnt) /* 치킨집 보다 많으면 종료 */
	{
		if (chickenCount == M) /* 선택된 치킨집이 M과 같을 때만 계산 */
		{
			int tmp = calculate();
			if (tmp < MIN) MIN = tmp;
		}

		return;
	}

	chickenList[L] = 1;
	DFS(L + 1, chickenCount + 1);

	chickenList[L] = 0;
	DFS(L + 1, chickenCount);
}

 

DFS를 시작하면, chickenList[Level] = 1 선택을 한다.

선택하였으므로 count를 1 올려서 다음 DFS를 보낸다.

이 DFS가 최종적으로 종료되면, 다음에는 선택하지 않은 경우를 만들어야 한다.

따라서 chickenList에 0을 넣고, count는 올리지 않는다.

 

치킨집이 5개이고, M = 3이라면 다음과 같은 list가 만들어진다.

 

[1, 1, 1, 0, 0] → chickenList[L] = 1에 의해 계속 1이 저장되다가, 

[1, 1, 1, 1, 0] → chickenCount = 4 > M = 3에 의해 종료되어 만들어 지지 않음.
[1, 1, 0, 1, 0] → L = 3에 0을 넣고 다음 DFS 시작. (chickenCount = 3, L = 4에 1이 만들어짐)

[1, 1, 0, 1, 1] → chickenCount = 4 > M = 3에 의해 종료되어 만들어 지지 않음.

[1, 1, 0, 0, 1] 
[1, 1, 0, 0, 0] → chickenCount 2 != 3 이므로, caluculate 하지 않음.
[1, 0, 1, 1, 0]
[1, 0, 1, 0, 1]
[1, 0, 1, 0, 0]
[1, 0, 0, 1, 1]
[1, 0, 0, 1, 0]
[1, 0, 0, 0, 1]
[1, 0, 0, 0, 0]
[0, 1, 1, 1, 0]
[0, 1, 1, 0, 1]
[0, 1, 1, 0, 0]
[0, 1, 0, 1, 1]
[0, 1, 0, 1, 0]
[0, 1, 0, 0, 1]
[0, 1, 0, 0, 0]
[0, 0, 1, 1, 1]
[0, 0, 1, 1, 0]
[0, 0, 1, 0, 1]
[0, 0, 1, 0, 0]
[0, 0, 0, 1, 1]
[0, 0, 0, 1, 0]
[0, 0, 0, 0, 1]
[0, 0, 0, 0, 0]

 

이러한 경우의 수 만들기 문제는 N과 M으로 연습하자.

위의 경우는 5개 중 3개를 고르는 조합의 응용이다.

 

만들어진 list에서 1이 3개인 경우만 아래의 계산을 하면 된다.

(집에 대해 모든 치킨집의 최소 거리 저장 후 누적)

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

	sum = 0;
	for (int i = 0; i < hcnt; i++)
	{
		tmp = 0;
		min = 0x7fff0000;
		for (int k = 0; k < ccnt; k++)
		{
			if (chickenList[k + 1] == 0) continue;
			min = minValue(min, getLength(house[i].r, house[i].c, chicken[k].r, chicken[k].c));
		}

		sum += min;
	}

	return sum;
}

 

최종 코드는 아래와 같다.

#include <stdio.h>

#define MAX (50 + 10)

int N, M;
int MAP[MAX][MAX];
int chickenList[MAX * 2];

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

RC house[MAX * 2];
RC chicken[13 + 5];
int hcnt, ccnt;

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);

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

			if (MAP[r][c] == 1)
			{
				house[hcnt].r = r;
				house[hcnt++].c = c;
			}
			else if (MAP[r][c] == 2)
			{
				chicken[ccnt].r = r;
				chicken[ccnt++].c = c;
			}
		}
	}
}

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

	sum = 0;
	for (int i = 0; i < hcnt; i++)
	{
		tmp = 0;
		min = 0x7fff0000;
		for (int k = 0; k < ccnt; k++)
		{
			if (chickenList[k + 1] == 0) continue;
			min = minValue(min, getLength(house[i].r, house[i].c, chicken[k].r, chicken[k].c));
		}

		sum += min;
	}

	return sum;
}


int MIN = 0x7fff0000;
void DFS(int L, int chickenCount)
{
	if (chickenCount > M) return;

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

		return;
	}

	chickenList[L] = 1;
	DFS(L + 1, chickenCount + 1);

	chickenList[L] = 0;
	DFS(L + 1, chickenCount);
}

int main(void)
{

	input();

	DFS(1, 0);

	printf("%d\n", MIN);

	return 0;
}

List[1]부터 값을 저장한다는 것에 주의하면 된다.

 

실제 A형에서는 tc가 여러 개이므로, MIN값을 초기화 하는 것을 잊지 말자.