글 읽기 - 치킨배달 문제 왜 틀린건지 모르겠네요 부탁드립니다

walrus44522 5년 전 0

테스트케이스는 다 맞게나오고 이상없는 것 같은데 어디부분이 잘못됫는지 모르겟네여

<code>
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

int N = 0;
int M = 0;
vector<vector<int>>  v;
bool visited[55][55];
int min_total_chickDistance = -1;
int cnt = 0;

//선택된 집의 인덱스 정보를 가지고 현재 선택된 m개의 치킨집 중 가장 가까운 거리를 계산
int chickenDistance(int a, int b)
{
	int min_distance = -1;

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (visited[i][j])
			{
				if (min_distance == -1|| (min_distance > (abs(a - i) + abs(b - j)) ))
				{
					min_distance = abs(a - i) + abs(b - j);
				}
			}
		}
	}
	return min_distance;
}


// 집을 먼저 찾음
int cal()
{
	int total_chickDistance = 0;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (v[i][j] == 1) 
			{
				total_chickDistance = total_chickDistance +  chickenDistance(i, j);
			}
		}
	}
	return total_chickDistance;
}

void dfs(int row,int col, int m)
{
	//치킨집 m개를 찾았으면 도시의 치킨거리를 계산함
	if (cnt == m) 
	{
		int total_chickDistance = cal();
		if (min_total_chickDistance == -1 || (min_total_chickDistance > total_chickDistance))
		{
			min_total_chickDistance = total_chickDistance;
		}
	}
	else
	{
		for (int i = row; i < N; i++)
		{
			for (int j = col; j < N; j++)
			{
				if (!visited[i][j] && v[i][j] == 2) // 치킨집이고 방문을 안했으면 
				{
					visited[i][j] = true;
					cnt++;

					dfs(i, j, m);

					cnt--;
					visited[i][j] = false;
					
				}
			}
		}
	}
}

int main()
{
	vector<int> temp;
	
	int input = 0;
	cin >> N;
	cin >> M;
	
	//visited = new bool*[N];
	for (int i = 0; i < N; i++)
	{
		v.push_back(temp);
		//visited[i] = new bool[N];
		for (int j = 0; j < N; j++)
		{
			cin >> input;
			v[i].push_back(input);
			visited[i][j] = false;
		}
	}

	// 치킨집 선택수가 1부터  M까지의 경우에 대해 진행
	for(int i = 1; i <= M; i++
        {
		dfs(0,0, M);
        }

	cout << min_total_chickDistance << endl;

	return 0;
}

walrus44522 5년 전 0

참고로 main문 밑에 for문은 게시글 작성하면서 잘못쓴 부분이고 실제론 제대로 동작합니다.

eric00513 5년 전 0

다음부터는 카테고리를 질문으로 하고, 문제 번호 칸에 치킨 배달 문제 번호를 입력해 주시면 좋을 것 같습니다.

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

문제

문제

출처

ICPC

치킨배달 문제 왜 틀린건지 모르겠네요 부탁드립니다

walrus44522 5년 전 0

walrus44522 5년 전 0

eric00513 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말