[C++] 백준 BOJ - 치킨 배달 (15686)

링크 : https://www.acmicpc.net/problem/15686

15686번: 치킨 배달

 

TIL

1) 풀면서 놓쳤던 점

놓쳤던건 아니고.. ㅎㅎ 뭔가 완전탐색 dfs일거같은데 영 감이 안왔다. 완전 초반 접근은 2차원 배열을 생각했다가, 굳이 필요 없을거라는 생각에 치킨집을 벡터로 뺐다. 그렇게 두니 자연스레 가정집도 분리하여 벡터로 뺐다.

dfs를 구현하고, 탈출조건 전까지 가정집 벡터를 돌며, 그 루프 안에서 폐업하지 않은 치킨집을 돌며 뭔가 치킨거리를 계산해야겠다고 생각했다.

근데 dfs구현이 너무무무무무 감이 안왔다. 아무래도 이런 문제를 스스로 푸는건 아직 .. 어렵다 흑흑 하지만 이제 대충 감이온다!! 아잣아잣 이 문제 까먹을때쯤 다시한번 풀어봐야겠다.

 

2) 이 문제를 통해 얻어갈 것

visual studio에서 테스트 케이스를 돌려볼땐 <cstdio>,<climits>, <vector> 헤더파일만 include된 상태였지만 잘 작동해서, abs함수가 기본 내장 함수 또는 앞서 언급한 헤더파일의 함수일거라 생각했다.

 

그렇게 백준에 코드를 제출했는데, visual studio에서와는 달리, abs 함수에서 컴파일 에러가 발생했다!

 

찾아보니, abs는 기본 내장함수가 아니었다.

몇개의 글을 찾아봤는데, <iostream>, <cmath>, <cstdlib> 등등 다양한 헤더파일이 언급됐다.

언급한 저 헤더파일에 모두 존재한다는거 같긴한데, 제일 무난하다고 생각한 iostream 헤더파일을 추가해 백준에 제출하니 컴파일 에러가 발생하지 않고 잘 작동하였다!

 

더 구체적으로 찾아봐야 알겠지만, 시험장에서 위와같은 상황이 발생하면  당황할수도 있으므로! 시험중엔 구글링이 안되니, 당황하지 말고 #define ABS를 하자 !

 

정답 코드

#include<cstdio>
#include<climits>
#include<vector>
#include<iostream>
int N, M,curr;
std::vector<std::pair<int, int>>chicken;
std::vector<std::pair<int,int>>home;
std::vector<int>distance;

void cal() {
	int sumdistance = 0;
	for (auto h : home) {
		int minch = INT_MAX;
		for (auto ch : chicken) {
			if (ch.first != -1) {
				if (abs(h.first - ch.first) + abs(h.second - ch.second) < minch) {
					minch = abs(h.first - ch.first) + abs(h.second - ch.second); //치킨거리
				}
			}
		}
		sumdistance += minch;
		//printf("치킨거리 : %d\n", sumdistance); // 치킨거리 계산 확인 테스트용
	}
	distance.push_back(sumdistance); // 치킨거리 push
	return;
}

void dfs(int idx, int rest) {
	if (rest == 0) { // 폐업 시켜야할 만큼 시킨경우
		cal();
		return;
	}
	if (idx > chicken.size() - 1) return;
	int backup = chicken[idx].first;
	chicken[idx].first = -1; // 폐업 처리
	dfs(idx + 1, rest - 1);
	chicken[idx].first = backup; // 폐업 아닐때
	dfs(idx + 1, rest);
	return;
}

int main() {
	scanf("%d %d", &N, &M);
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			scanf("%d", &curr);
			if (curr == 2) chicken.push_back({ i,j });
			else if (curr == 1) home.push_back({ i,j });
		}
	}
	dfs(0,chicken.size() - M);// 도시의 치킨거리가 가장 작게 되는 M개의 치킨집을 남기기

	int minD = INT_MAX; // 최소 치킨거리
	for (auto d : distance) { // distance 벡터 중 최솟값 찾아 출력
		if (d < minD) {
			minD = d;
		}
	}
	printf("%d", minD);
	return 0;
}