글 읽기 - 치킨배달 질문드립니다.

kjho1037 5년 전 0

기존 DFS후, BFS로 치킨 거리 구하였는데...시간이 280msec으로 거의 꼴지 수준이더군요!!

그래서 집들의 위치를 아니까 BFS할 필요가 없을 것 같아 아래와 같이 풀어보았습니다.

주석은 달긴 달았는데...부족하시면 말씀해주세요!!

테케는 다 맞는데...넣자마자 제출하자마자ㅜ,ㅠ

#include <stdio.h>
#include <string.h>

int map[55][55];

point Res[13];
int Res_visit[13];

point House[13];
int House_visit[13];

int N, M, Res_count, House_count, MIN;

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

void DFS(int Cur, int m)
{
	if (m == M)
	{
		int Chicken_map[55][55] = { 0, };

		for (int i = 0; i < 55; i++)
		{
			for (int j = 0; j < 55; j++)
			{
				Chicken_map[i][j] = 987654321;
			}
		}

		for (int i = 0; i < Res_count; i++)
		{
			if (Res_visit[i] == 1)
			{
				for (int j = 0; j < House_count; j++)
				{
					int a = Chicken_map[House[j].y][House[j].x];//기존의 치킨 거리
					int b = abs(House[j].y, Res[i].y) + abs(House[j].x, Res[i].x);//새로운 치킨집으로 부터의 치킨 거리
					Chicken_map[House[j].y][House[j].x] = a < b ? a : b;//더 작은 값으로 갱신
				}
			}
		}

		int total = 0;

		for (int j = 0; j < House_count; j++)
		{
			total += Chicken_map[House[j].y][House[j].x];
		}
		if (total < MIN)
			MIN = total;

		return;
	}

	for (int i = Cur + 1; i < Res_count; i++)
	{
		Res_visit[i] = 1;
		DFS(i, m + 1);
		Res_visit[i] = 0;
	}
	return;
}

int main()
{
	scanf("%d %d", &N, &M);
	memset(map, -1, sizeof(map));
	MIN = 987654321;
	for (int a = 1; a <= N; a++)
	{
		for (int b = 1; b <= N; b++)
		{
			scanf("%d", &map[a][b]);
			if (map[a][b] == 2)//치킨 입력
			{
				Res[Res_count].y = a;
				Res[Res_count].x = b;
				Res_count++;
			}
			else if (map[a][b] == 1)//집 입력
			{
				House[House_count].y = a;
				House[House_count].x = b;
				House_count++;
			}
		}
	}

	for (int i = 0; i < Res_count; i++)//M개 추리자~
	{
		Res_visit[i] = 1;
		DFS(i, 1);
		Res_visit[i] = 0;
	}

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

	return 0;
}

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

문제

문제

출처

ICPC

치킨배달 질문드립니다.

kjho1037 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말