C# 14889번 스타트와 링크

문제

using System;
using System.Text;

namespace beakjoon
{
    class _8
    {
        static int range, length;
        static int[] tempArr = new int[21];
        // 값 출력을 위한 정수 배열
        static int[] arr = new int[21];
        // 값 출력을 위한 정수 배열
        static string[] awaytemp = new string[21];
        // 값 출력을 위한 정수 배열
        static int[] awayArr = new int[21];
        // 중복 제거를 위한 bool 배열
        static bool[] visited = new bool[21];
        // 2차원 배열
        static int[,] all = new int[21, 21];
        static StringBuilder output = new StringBuilder();

        static int min = 1000000000;
        static int arrsum, awaysum;
        
        //DFS 알고리즘
        public static void DFS(int cnt)
        {
            // 출력할 배열이 완성되면 문자열 출력
            if (cnt == length)
            {
                StringBuilder sb = new StringBuilder();
                StringBuilder sb2 = new StringBuilder();
                
                //팀을 두팀으로 나누는 과정 중 AWAY팀 만드는 과정
                for (int i = 1; i <= range; i++)
                {
                    //HOME팀에 있으면 넘어간다.
                    if (Array.Exists(arr, element => element == i))
                    {
                        continue;
                    }
                    //없을 경우 어웨이팀으로 간다.
                    else
                    {
                        sb2.Append($"{i} ");
                    }
                }
                
                for (int i = 0; i < length; i++)
                {
                    sb.Append($"{arr[i]} ");
                }
                awaytemp = sb2.ToString().Split(' ');
                
				//AWAY팀 배열 완성
                for (int i = 0; i < length; i++)
                {
                    awayArr[i] = Convert.ToInt32(awaytemp[i]);
                }
                
                //전체 2차원 행렬에서 각 팀별 시너지를 모두 추출하고 합하는 과정
                for (int i = 0; i < length; i++)
                {
                    for (int j = 0; j < length; j++)
                    {
                        if (i == j)
                            continue;
                        else
                        {
                            //HOME팀 시너지의 합
                            arrsum += all[arr[i], arr[j]];
                            //AWAY팀 시너지의 합
                            awaysum += all[awayArr[i], awayArr[j]];
                        }
                    }                    
                }
                if (min > Math.Abs(arrsum - awaysum))
                    min = Math.Abs(arrsum - awaysum);
                    
                //초기화
                arrsum = 0;
                awaysum = 0;
            }

            // 문자열 완성이 안됬을 시 반복
            else
            {
                for (int i = 1; i <= range; i++)
                {
                    if (!visited[i])
                    {
                        if ((cnt > 0 && arr[cnt - 1] < i) || cnt == 0)
                        {
                            visited[i] = true;
                            arr[cnt] = i;
                        }
                        else
                        {
                            continue;
                        }
                        // 재귀 호출
                        DFS(cnt + 1);

                        // 다음 문자열 생성을 위해 bool 초기화
                        visited[i] = false;
                    }
                }
            }
        }

        public static void Main(string[] args)
        {
            int temp = Convert.ToInt32(Console.ReadLine());
            for (int i = 0; i < temp; i++)
            {
                tempArr[i] += i;
            }
            for (int i = 1; i <= temp; i++)
            {

                string temp2 = Console.ReadLine();
                string[] temp3 = temp2.Split(' ');
                for (int j = 1; j <= temp; j++)
                {
                    all[i, j] = Convert.ToInt32(temp3[j-1]);
                }
            }
            //수열의 범위 
            range = temp;

            //문자열의 길이
            length = temp / 2;

                       

            DFS(0);
            Console.WriteLine(min);
        }
    }
}

코드 설명 :

문제를 먼저 이해할 필요가 있다.

만약 6명이서 축구를 할것이고 1,3,6 을 한 팀(HOME팀)이고 2,4,5를 한 팀(AWAY팀)으로 한다면 

HOME에서 더해야할 모든 시너지는 S13, S16, S31, S36, S61, S63 이다.

AWAY에서 더해야할 모든 시너지는 S24, S25, S42, S45, S52, S54 이다.

이를 이해하고 넘어가야한다.

그렇다면 풀이과정은 간단하다. 먼저 팀을 반으로 쪼개고 팀을 만들 수 있는 모든 경우의 수에 대해 HOME팀과 AWAY팀으로 나누어 시너지를 구하고 이 차이가 가장 적은 값을 출력하면 된다.

 

느낀점 :

두팀으로 나누는 과정에서 특히 AWAY팀을 만드는 과정에서 형변환이 너무 많이 일어나고 쓸때없는 변수를 많이 이용하는것 같아 아쉽다. 이부분의 최적화가 필요하다.