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

안녕하세요 평범한 컴공생입니다.

 

오늘은 백준 15686번 [치킨 배달] 문제 알고리즘입니다.

삼성 SW역량테스트 기출문제입니다.

 

처음 문제를 맞닥뜨리고 집합에서의 조합을 어떻게 컴퓨터 언어로 풀어낼 수 있을까 많이 고민해 보았습니다.

사실 이 문제를 저의 능력으로 푼 것이 아니라 다른 분의 알고리즘을 보고 참고하여 푼 것이라 아직 실력이 정말 많이 ㅈ부족하다는 것을 느낄 수 있었던 문제였습니다.

이 풀이가 아니라 구글링을 통해 보았던 다른 분들의 풀이를 보면 C++의 vector를 많이 활용한 것을 알 수 있었는데 아직 vector 의 개념을 학습하지 않아 vector 개념을 조만간 학습한 후에 다시 이 문제를 접근해 보려고 합니다. 

골드 5 난이도의 문제입니다.

1. 문제 해결 방법 구상하기

 - 크기가 N*N인 도시의 정보와 남겨놓을 치킨집의 개수 M을 입력받아야 하므로 행과 열을 나타낼 이중반복문을 활용해야한다.

 - 만약 일반 가정집 (1)을 입력받았다면 그 행과 열의 정보를 가정집의 배열에 기록해 두어야 하고, 치킨집(2)을 입력받았다면 그 행과 열의 정보를 치킨집의 배열에 기록해 두어야 한다. >> 이를 위해 입력받은 치킨집과 가정집의 개수를 count 해줄 전역변수를 선언해주어야 할 것이고, 행과 열의 정보는 구조체(struct)를 통해 입력받으면 된다.

 - solution 함수를 통해 바로 답을 출력하도록 하고 solution 함수에 문제에서 원하는 치킨 거리를 구하도록 알고리즘을 짜야한다.

 - 입력받은 치킨집의 개수를 전역변수 Cnt_Chicken 이라고 하면 집합 Cnt_Chicken의 원소 중 M개의 원소만 남아있을 경우들만 비교를 해주면 된다. >> 그렇다면 어떻게 M개의 원소, 즉 Cnt_Chicken 콤비네이션 M 의 경우의 수를 표현할 것인가? >> 비트를 통해서 표현해주면 된다.

 - algorithm 라이브러리를 include 하여 min 함수를 사용하여 최단거리를 계속 갱신해주면 될 듯하다.

 

2. 구상한 아이디어를 바탕으로 코딩하기

#include <iostream>
#include <algorithm> // min 함수 사용을 위해

#define BIG_NUM 987654321 // 매우 큰 값을 설정해주어 무조건 첫 경우가 작은 값으로 갱신되도록

using namespace std;

struct location
{
	int row, col;
};	// 입력받은 가정집과 치킨집의 위치정보(행과 열)을 저장하기 위한 구조체

int N, M; // 전역변수로 N, M을 입력받아 solution 함수에 다시 M값을 인자로 넣지 않아도 되도록 함
location House[100], Chicken[13]; // 가정집과 치킨집의 주소정보 저장하는 구조체
int Cnt_House = 0, Cnt_Chicken = 0; 입력받는 치킨집과 가정집의 개수

int abs(int n)
{
	return n >= 0 ? n : -n;
}	// 절댓값을 반환해주는 함수

int bitchk(int n)
{
	int cnt = 0;
	while (n)
	{
		if (n & 1)
			cnt++;
		n = n >> 1;
	}
	return cnt;
}	// Cnt_Chicken 콤비네이션 M 의 경우만 색출해주는 함수
	// n을 이진수로 봤을 때 비트를 이용해 해당 치킨집을 없앨지 말 지를 설정해줄 수 있음

int solution()
{
	int ans = BIG_NUM;
	for (int set = 0; set < (1 << Cnt_Chicken); set++)
	{	// 원소의 개수가 Cnt_Chicken인 집합의 부분집합의 개수는 2의 Cnt_Chicken 제곱이므로
    	// 1 << Cnt_Chicken 해주면 된다.
		if (bitchk(set) == M)
		{
			int sum=0;
			for (int i = 0; i < Cnt_House; i++)
			{
				int distance = BIG_NUM;
				for (int j = 0; j < Cnt_Chicken; j++)
				{
					if (set & (1 << j))
						distance=min(distance,
							abs(House[i].row - Chicken[j].row) + abs(House[i].col - Chicken[j].col));
				}
				sum += distance;
			}
			ans = min(ans, sum);
		}
	}
	return ans;
}

int main()
{
	cin >> N >> M;

	int input;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cin >> input;
			if (input == 1)
				House[Cnt_House++] = { i,j };
			else if (input == 2)
				Chicken[Cnt_Chicken++] = { i,j };
		}
	}

	cout << solution() << endl;

	return 0;
}

생각보다 참 난항을 했던 문제였고, 더 공부에 절실히 매달려야 함을 알려준 문제였다. 그리고 삼성 SW 기출문제이므로 멀지 않은 미래에 이러한 문제를 맞닥뜨리게 될텐데, 그 미래에는 당황하지 않고 차분히 해결할 수 있는 실력을 갖춘 개발자로 성장해있기를 바라며 앞으로 더 노력해야겠다.

 

// 피드백 및 문제사항 제기 감사히 받겠습니다.