[백준] 25824 - 빠른 오름차순 메세지 전달

1. 문제

25824번: 빠른 오름차순 메시지 전달

2. 개요

1번부터 12번까지의 학생이 있다.

학생은 1번부터 번호순으로 두 명씩 한 그룹으로 묶인다.

선생님은 긴급 메세지를 학생 모두에게 전달하려고 한다.

선생님 → 그룹 1 → 그룹 2 → … → 그룹 6 의 순서대로 전달하며 12명의 학생 모두가 메세지를 받으면 전달이 완료된다.

12 x 12 행렬로 학생 i가 j에게 보내는 시간이 주어졌을 때, 가장 빠르게 메세지 전달을 완료할 수 있는 시간을 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

조건이 있는 순열을 만들어 답을 찾아내는 문제.

먼저 (1번 그룹) (2번 그룹) (3번 그룹) … (6번 그룹) 인 순열을 백트래킹으로 구한다.

구한 순열 및 주어진 행렬을 가지고 최소 시간이 되는 경우를 구한 뒤 답을 출력한다.

3-2. Python

import sys

seconds = []

answer = 13000

for i in range(12):
    seconds.append(list(map(int, sys.stdin.readline().split())))

visited = [False for i in range(12)]

def BT(idx, l):
    global answer
    if idx == 12:
        tmp = 0

        for i in range(1, 12):
            tmp += seconds[l[i]][l[i-1]]

        answer = min(tmp, answer)

    else:
        if idx % 2 == 0:
            for i in range(idx, idx + 2):
                if visited[i] == False:
                    visited[i] = True
                    BT(idx + 1, l + [i])
                    visited[i] = False

        else:
            for i in range(idx - 1, idx + 1):
                if visited[i] == False:
                    visited[i] = True
                    BT(idx + 1, l + [i])
                    visited[i] = False

BT(0, [])
print(answer)

3-3. C#

namespace boj_25824
{
    internal class Program
    {
        static int[,] seconds;
        static bool[] visited;
        static int answer;

        static void Main(string[] args)
        {
            seconds = new int[12, 12];
            visited = new bool[12];
            answer = 13000;

            for (int i = 0; i < 12; i++)
            {
                string[] input = Console.ReadLine().Split();

                for (int j = 0; j < 12; j++)
                {
                    seconds[i, j] = int.Parse(input[j]);
                }
            }

            BT(0, new List<int>());
            Console.WriteLine(answer);
        }

        static void BT(int idx, List<int> l)
        {
            if (idx == 12)
            {
                int tmp = 0;

                for (int i = 1; i < 12; i++)
                    tmp += seconds[l[i], l[i - 1]];

                answer = (int)MathF.Min(tmp, answer);
            }

            else
            {
                if (idx % 2 == 0)
                {
                    for (int i = idx; i < idx + 2; i++)
                    {
                        if (visited[i] == false)
                        {
                            visited[i] = true;
                            BT(idx + 1, l.Append(i).ToList());
                            visited[i] = false;
                        }
                        
                    }
                }

                else
                {
                    for (int i = idx - 1; i < idx + 1; i++)
                    {
                        if (visited[i] == false)
                        {
                            visited[i] = true;
                            BT(idx + 1, l.Append(i).ToList());
                            visited[i] = false;
                        }
                    }
                }
            }
        }
    }
}