난이도

Gold 5

인증

문제

선생님 1명과 학생 12명이 있다. 학생에게 1번부터 12번까지 번호가 부여된다. 학생들은 두 명씩 하나의 친구 집단을 이룬다. 1번 학생부터 번호순으로 두 명씩 하나의 친구 집단에 포함된다. 즉, 친구 집단 1은 {학생 1번, 학생 2번}, 친구 집단 2는 {학생 3번, 학생 4번}, … , 친구 집단 6은 {학생 11번, 학생 12번}으로 구성된다.

선생님은 긴급 메시지를 12명 학생 모두에게 최대한 빠르게 전달하려고 한다. 선생님은 긴급 메시지를 친구 집단 1에 전달한다. 선생님으로부터 메시지를 전달받은 1번 또는 2번 학생은 같은 친구 집단에 있는 다른 친구 2번 또는 1번 학생에게 메시지를 전달한다. 메시지를 전달받은 1번 학생 또는 2번 학생은 친구 집단 2에 메시지를 전달한다. 메시지를 받은 친구는 앞에서 언급된 내용과 같은 방식으로 친구 집단 내에 다른 친구에게 메시지를 전달하고 메시지를 전달받은 친구는 친구 집단 3에 메시지를 전달한다. 친구 집단 4, 친구 집단 5, 친구 집단 6 순서대로 메시지를 전달하고 12명의 학생이 모두 메시지를 받으면 선생님의 메시지 전달이 완료된다. 선생님은 첫 번째 학생에게 메시지를 즉시 전달하기 때문에 첫 번째 학생이 메시지를 받는 데 걸리는 시간은 0으로 생각한다. 12명의 학생이 다른 친구에게 메시지를 전달하는 데 걸리는 시간이 주어지면, 친구 집단 1부터 친구 집단 6 순서대로 12명의 친구에게 메시지를 전달하는데 걸리는 최소 시간을 출력하자.

입력

첫 번째 줄부터 열두 개의 줄에 걸쳐 메시지를 전달하는 데 걸리는 시간이 주어진다. i번째 줄의 j번째 숫자는 학생 i가 학생 j에게 메시지를 전달하는 데 걸리는 시간을 나타낸다.

출력

첫 번째 줄에 친구 집단 1부터 친구 집단 6 순서대로 12명의 친구에게 메시지를 전달하는데 걸리는 최소 시간을 출력한다.

예제 입력

0 1 2 3 1 1 1 1 1 1 1 1
1 0 3 4 1 1 1 1 1 1 1 1
2 3 0 2 2 9 1 1 1 1 1 1
3 4 2 0 1 5 1 1 1 1 1 1
1 1 2 1 0 3 3 6 1 1 1 1
1 1 9 5 3 0 9 2 1 1 1 1
1 1 1 1 3 9 0 5 3 7 1 1
1 1 1 1 6 2 5 0 7 2 1 1
1 1 1 1 1 1 3 7 0 1 7 4
1 1 1 1 1 1 7 2 1 0 3 3
1 1 1 1 1 1 1 1 7 3 0 1
1 1 1 1 1 1 1 1 4 3 1 0

예제 출력

24

해설 및 후기

복잡해 보이지만 그렇지 않다. 다음 집단으로 넘어가는 방법이 많지 않기 때문이다. 집단이 a,b 일때, a로 전달된 경우 b에게 메시지를 보내고 b에서 다음 집단의 a로 보내거나, b로 보낸다. b로 전달된 경우 a에게 메시지를 보내고 a에서 다음 집단의 a로 보내거나 b로 보낸다. 위와 같이 경우의 수가 많지 않기 때문에 dfs로 완전 탐색을 구현하여 최소 시간을 구한다.

제출 코드

import sys
time = []
for i in range(12):
    time.append(list(map(int, sys.stdin.readline().rstrip().split())))
minTime = 12*10000
def dfs(n,usedTime):
    global minTime
    if(usedTime > minTime):
        return
    if(n>=10): #마지막 집단에 도착
        usedTime += time[10][11] if n==10 else time[11][10]
        if(usedTime < minTime):
            minTime = usedTime
        return
    elif(n%2 == 1): #집단에서 두번째 자리에 전달됨
        usedTime += time[n][n-1]
        dfs(n+1, usedTime+time[n-1][n+1]) #다음 집단의 첫번째에 보내거나
        dfs(n+2, usedTime+time[n-1][n+2]) #다음 집단의 두번째에 보냄
    else:
        usedTime += time[n][n+1]
        dfs(n+2, usedTime+time[n+1][n+2])
        dfs(n+3, usedTime+time[n+1][n+3])
dfs(0,0)
dfs(1,0)
print(minTime)