SW Expert Academy 2383. [모의 SW 역량테스트] 점심 식사시간

문제 링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5-BEE6AK0DFAVl

SW Expert Academy

문제의 핵심은 먼저 각 사람이 어느 계단으로 갈 것인가를 정하고, 이후에 각 계단에서의 상황을 잘 구현하는가의 문제이다. 나는 먼저 각 사람이 어느 계단에 갈 것인지를 정하는 것을 큐에 담아서 결정하였다. 큐에 사람 수만큼의 결정이 이루어지면 각 계단마다 상황을 계산하여 두 계단 중 머물러 있는 시간의 최댓값을 반환하는 함수를 만들었다. 아래는 내가 구현한 코드이다.

from collections import deque

# 모든 사람들이 어느 계단으로 갈지가 정해지면 시간을 반환하는 함수
def result(s1, s2, t1, t2):
    max1 = 0
    max2 = 0
    dic1 = {}
    dic2 = {}
    s1.sort()
    s2.sort()
    if s1:
        for p in s1:
            c = 0
            m = p+1
            while c < t1:
                if dic1.get(m) is None:
                    dic1[m] = 1
                    c += 1
                    m += 1
                elif dic1.get(m) < 3:
                    dic1[m] += 1
                    c += 1
                    m += 1
                elif dic1.get(m) == 3:
                    m += 1
        max1 = list(dic1.keys())[-1]
    if s2:
        for p in s2:
            c = 0
            m = p+1
            while c < t2:
                if dic2.get(m) is None:
                    dic2[m] = 1
                    c += 1
                    m += 1
                elif dic2.get(m) < 3:
                    dic2[m] += 1
                    c += 1
                    m += 1
                elif dic2.get(m) == 3:
                    m += 1
        max2 = list(dic2.keys())[-1]
    return max(max1, max2)+1


def solution(people, stairs):
    answer = float('inf')
    num = len(people)
    times = []
    for p in people:
        sub = []
        for st in stairs:
            sub.append(abs(p[0] - st[0]) + abs(p[1] - st[1]))
        times.append(sub)
    queue = deque()
    queue.append([0, [], []])
    while queue:
        cnt, st1, st2 = queue.popleft()
        if cnt == num:
            sub = result(st1, st2, stairs[0][2], stairs[1][2])
            if answer > sub:
                answer = sub
        else:
            queue.append([cnt + 1, st1 + [times[cnt][0]], st2])
            queue.append([cnt + 1, st1, st2 + [times[cnt][1]]])
    return answer


t = int(input())
for test in range(1, t + 1):
    n = int(input())
    stairs = []
    people = []
    for i in range(n):
        s = list(map(int, input().split()))
        for j in range(n):
            if s[j] == 1:
                people.append([i, j])
            elif s[j] > 1:
                stairs.append([i, j, s[j]])
    ans = solution(people, stairs)
    print('#{} {}'.format(test, ans))