[알고리즘 문제 풀기] 치킨 배달(15686)

1. 문제 풀이 아이디어

• 집과 치킨집의 위치를 저장한 후, 각 집에서 모든 치킨집까지의 거리를 계산하여 정렬한다.

• m개의 치킨집을 선택하는 조합을 백트래킹으로 구현하고, 선택된 치킨집들로부터 도시의 치킨 거리를 계산한다.

• 비트마스크를 활용하여 선택된 치킨집을 관리하고, 최소 치킨 거리를 갱신하여 문제를 해결한다.

2. 나의 정답 코드

using (StreamReader sr = new StreamReader(Console.OpenStandardInput()))
using (StreamWriter sw = new StreamWriter(Console.OpenStandardOutput()))
{
    string[] split = sr.ReadLine().Split();
    int n = int.Parse(split[0]);
    int m = int.Parse(split[1]);

    List<int[]> house = new List<int[]>();
    List<int[]> chicken = new List<int[]>();
    for (int i = 0; i < n; i++)
    {
        split = sr.ReadLine().Split();
        for (int j = 0; j < n; j++)
        {
            if (split[j][0] == '0') continue;
            if (split[j][0] == '1') house.Add(new int[] { i, j });
            else chicken.Add(new int[] { i, j });
        }
    }
    int[][][] dist = new int[house.Count][][];
    for (int i = 0; i < house.Count; i++)
    {
        int[] curH = house[i];
        dist[i] = new int[chicken.Count][];
        for (int j = 0; j < chicken.Count; j++)
        {
            int[] curC = chicken[j];
            dist[i][j] = new int[2];
            dist[i][j][0] = 1 << j;
            dist[i][j][1] = Math.Abs(curH[0] - curC[0]) + Math.Abs(curH[1] - curC[1]);
        }
        Array.Sort(dist[i], (a, b) => a[1].CompareTo(b[1]));
    }
    int remain = 0;
    int result = int.MaxValue;
    Solve(0, 0);
    sw.WriteLine(result);
    void Solve(int count, int start)
    {
        if (count == m)
        {
            int sum = 0;
            for (int i = 0; i < house.Count; i++)
            {
                int j = 0;
                while ((remain & dist[i][j][0]) == 0) j++;
                sum += dist[i][j][1];
                if (sum > result) return;
            }
            result = Math.Min(sum, result);
            return;
        }
        for (int i = start; i < chicken.Count; i++)
        {
            remain += 1 << i;
            Solve(count + 1, i + 1);
            remain -= 1 << i;
        }
    }
}

3. 정리

• house 리스트에 집의 좌표를 저장하고, chicken 리스트에 치킨집의 좌표를 저장한다.

• dist[i][j]는 i번째 집에서 j번째 치킨집까지의 거리와 해당 치킨집의 인덱스를 비트마스크로 저장한 후 거리 순으로 정렬한다.

• 백트래킹을 이용해 remain 변수에 선택한 치킨집을 비트마스크로 저장한다.

• 선택된 m개의 치킨집에 대해, 각 집에서 가장 가까운 치킨집까지의 거리만 합산하여 최소값을 갱신해 문제를 해결한다.