백트래킹 - 4251

문제 설명

영어로 되어있지만 문제 해석을 하자면 데이터 셋의 갯수인 K, 부서진 수도관의 갯수 n, 수리트럭의 이동속도 v와 부서진 수도관의 정보들인 좌표 x,y 그리고 누수가 될 시간 t, 누수량 r이 주어졌을 때 누수량이 최소로 되게 하는 경로를 찾아서 최소 누수량을 출력하는 문제이다.

 

문제에 쓰이는 알고리즘 파악

이 문제는 백트래킹으로 구분되어 있다.

백트래킹이란?

브루트포스 알고리즘과 dfs(깊이 우선 탐색) 알고리즘과 유사하지만 해당 경로가 답을 찾을 가능성이 없으면 마지막으로 기록해둔 정점으로 돌아가는 로직이 추가된 방법이다.

 

문제 풀이

아래는 코드이다.

using System;
using System.Collections.Generic;

namespace StudyCS
{
    public struct WaterBreak
    {
        // xy는 좌표값
        // t는 시간
        // r는 누수량
        public double X;
        public double Y;
        public double T;
        public double R;
    }
    public class Problem
    {
        // n은 부서진 수도관의 갯수
        public int n = 0;

        // v는 수리 트럭의 수리 속도
        public double v = 0;

        // 파손 정보 배열
        public List<WaterBreak> breaks = new List<WaterBreak>();

        // 최소 누수량
        public double minTotalLeakage = double.MaxValue;

        public void GetWaterBreak(string[] input)
        {
            double[] inputToDouble = Array.ConvertAll(input, double.Parse);
            WaterBreak waterBreak = new WaterBreak
            {
                X = inputToDouble[0],
                Y = inputToDouble[1],
                T = inputToDouble[2],
                R = inputToDouble[3]
            };
            breaks.Add(waterBreak);
        }

        public double Solve()
        {
            List<int> path = new List<int>();
            bool[] visited = new bool[n];

            GetPath(path, visited);

            return minTotalLeakage;
        }

        public double CalculateLeakage(List<int> path)
        {
            double totalLeakage = 0;
            double currentTime = 0;
            double currentX = 0;
            double currentY = 0;

            for (int i = 0; i < n; i++)
            {
                WaterBreak targetWaterBreak = breaks[path[i]];
                double distance = Math.Sqrt(Math.Pow(targetWaterBreak.X - currentX, 2) + Math.Pow(targetWaterBreak.Y - currentY, 2));
                double travelTime = distance / v;
                double arrivalTime = currentTime + travelTime;

                double repairStartTime = Math.Max(arrivalTime, targetWaterBreak.T);
                double leakageForThisBreak = (repairStartTime - targetWaterBreak.T) * targetWaterBreak.R;
                totalLeakage += leakageForThisBreak;

                currentTime = repairStartTime;
                currentX = targetWaterBreak.X;
                currentY = targetWaterBreak.Y;
            }
            return totalLeakage;
        }

        public void GetPath(List<int> path, bool[] visited)
        {
            if (path.Count == n)
            {
                double nowLeakage = CalculateLeakage(path);
                minTotalLeakage = Math.Min(minTotalLeakage, nowLeakage);
                return;
            }
            for (int i = 0; i < n; i++)
            {
                if(!visited[i])
                {
                    visited[i] = true;
                    path.Add(i);

                    GetPath(path, visited);

                    path.RemoveAt(path.Count - 1);
                    visited[i] = false;
                }
            }
        }
    }
    class Program
    {
        public static void Main(string[] args)
        {
            // K는 주어지는 데이터 셋의 크기
            int K = int.Parse(Console.ReadLine().ToString());
            Problem[] problems = new Problem[K];

            //입력받기
            //데이터 셋의 갯수만큼 반복
            for (int i = 0; i < K; i++)
            {
                string[] secondInput = Console.ReadLine().ToString().Split();
                problems[i] = new Problem();
                problems[i].n = int.Parse(secondInput[0]);
                problems[i].v = double.Parse(secondInput[1]);
                bool[] visitedArray = new bool[problems[i].n];
                //지금 수도관의 갯수만큼 반복
                for (int j = 0; j < problems[i].n; j++)
                {
                    string[] input = Console.ReadLine().ToString().Split();
                    problems[i].GetWaterBreak(input);
                }
            }
            for (int i = 0; i < K; i++)
            {
                double result = problems[i].Solve();
                Console.WriteLine($"Data Set {i+1}:");
                Console.WriteLine($"{result:F2}");
                Console.WriteLine();
            }
        }
    }
}

코드 설명

처음에 어떻게 접근해야할지 막막했지만 다음과 같은 과정으로 해결하였다.

1. 우선 시작점부터 끝지점까지 경로를 기록한다.
2. 하나의 경로가 완성되면 현재 경로의 누수량을 계산한다.
   1. 이 때 각 정점에서의 누수량을 더하는 방식으로 계산한다.
   2. 현재 정점에서 누수량의 합이 최소 누수량보다 큰 경우 계산을 넘긴다.

하지만 위 코드를 보다보면 의아한 점이 있을 것이다. 2-2의 현재 정점에서 누수량의 합이 최소 누수량보다 큰 경우가 빠져있기 때문이다.

코드 추가

아래는 해당 부분만 수정된 코드이다.

// 파라미터로 현재 시간과 누적 누수량을 함께 전달
public void GetPath(List<int> path, bool[] visited, double currentTime, double currentLeakage)
{
    // 가지치기(Pruning): 현재 누수량이 이미 찾은 최솟값보다 크면 더 탐색하지 않음
    if (currentLeakage >= minTotalLeakage)
    {
        return;
    }

    // 종료 조건: 모든 지점을 방문한 경우
    if (path.Count == n)
    {
        minTotalLeakage = Math.Min(minTotalLeakage, currentLeakage);
        return;
    }

    // 다음 지점 탐색
    for (int i = 0; i < n; i++)
    {
        if (!visited[i])
        {
            // 다음 지점으로 이동했을 때의 상태를 미리 계산
            WaterBreak nextBreak = breaks[i];
            double lastX = (path.Count == 0) ? 0 : breaks[path.Last()].X;
            double lastY = (path.Count == 0) ? 0 : breaks[path.Last()].Y;

            double distance = Math.Sqrt(Math.Pow(nextBreak.X - lastX, 2) + Math.Pow(nextBreak.Y - lastY, 2));
            double arrivalTime = currentTime + (distance / v);
            double repairStartTime = Math.Max(arrivalTime, nextBreak.T);
            double newLeakage = (repairStartTime - nextBreak.T) * nextBreak.R;

            // 상태 변경 후 재귀 호출
            visited[i] = true;
            path.Add(i);

            GetPath(path, visited, repairStartTime, currentLeakage + newLeakage);

            // 상태 복구 (백트래킹)
            path.RemoveAt(path.Count - 1);
            visited[i] = false;
        }
    }
}

계산하는 누적된 누수량이 최소 누수량보다 클 경우 탐색하지 않고 넘어가는 방식이다.

이 방식까지 적용되어야 최적화된 백트래킹 알고리즘이라고 볼 수 있다.