[SWEA 2383] 점심 식사시간

접근

먼저 계단은 무조건 2개가 존재하고 사람의 수는 10명 이하이다. 따라서 완전탐색으로 풀 수 있었다. 

최대 10명의 사람들이 1번 또는 2번 계단을 고르는 모든 경우의 수를 만들고 

같은 계단을 고른 사람들 끼리 그룹을 만들어 해당 그룹의 사람들이 계단을 타고 모두 내려오는 시간을 구하는 함수를 만들었다. 이를 통해 1번과 2번 계단을 선택한 사람의 소요시간을 구하고 이 중 최댓값을 찾아 최종해와 최솟값 비교를 진행한다.

 

구현

- DFS를 통해 사람들의 1번 또는 2번 계단을 고르는 모든 경우의 수를 구한다.

- 사람들이 모두 계단을 골랐으면 1번 계단을 고른 사람과 2번 계단을 고른 사람을 나누고 이를 solve함수에 전달한다.

- solve 함수에서는 해당 사람들이 모두 내려왔을 때의 시간을 구하고 

- 두 개의 시간을 비교해 최댓값이 모든 사람들이 내려왔을 때의 시간이 된다.

- 이제 이 시간을 최종해와 비교하여 최솟값을 갱신한다.

def dfs(idx, selected):
    global answer
    if idx == M:
        first_stair = []
        second_stair = []
        for i in range(M):
            if selected[i]:
                first_stair.append(people_list[i])
            else:
                second_stair.append(people_list[i])
        time = max(solve(first_stair, stair_list[0][0], stair_list[0][1], stair_list[0][2]), solve(second_stair, stair_list[1][0], stair_list[1][1], stair_list[1][2]))
        answer = min(answer, time)
        return

    selected[idx] = True
    dfs(idx + 1, selected)
    selected[idx] = False
    dfs(idx + 1, selected)

- 먼저 해당 그룹의 사람들이 계단까지 이동하는 시간을 members에 저장하고 오름차순으로 정렬한다.

- waiting은 기다리고 있는 사람들이고 down_stair는 내려가고 있는 사람들을 저장한다.

- while문을 통해 모든 사람들이 계단을 타고 내려가도록 구현한다.

- 먼저 time을 증가시키고 내려가고 있는 사람이 있고, 해당 사람들이 time보다 이하이면(이미 내려간 것) 제거한다.

- 이제 그룹의 사람들 중 계단에 도착한 사람들을 waiting에 옮긴다.

- 이후 만약에 내려가고 있는 사람이 3명 미만일 때는 기다리고 있는 사람들 중 계단을 내려가도 되는 사람들을 dow_stair에 보낸다.

- while문을 한 번 돌 때마다 그룹의 사람들, 기다리고 있는 사람들, 내려가고 있는 사람들이 모두 없을 때 종료하도록 한다.

def solve(group, stair_y, stair_x, K):
    members = []
    for y, x in group:
        dist = abs(stair_y - y) + abs(stair_x - x)
        members.append(dist)
    members = deque(sorted(members))
    waiting = deque()
    down_stair = deque()
    time = 0
    while True:
        time += 1
        while down_stair and down_stair[0] <= time:
            down_stair.popleft()
        while members and members[0] <= time:
            members.popleft()
            waiting.append(time)

        if len(down_stair) >= 3:
            continue
        while waiting and waiting[0] + 1 <= time and len(down_stair) < 3:
            waiting.popleft()
            down_stair.append(time + K)


        if len(members) == 0 and len(waiting) == 0 and len(down_stair) == 0:
            break

    return time

---

전체 코드

import sys
from collections import deque
input = sys.stdin.readline

test_case = int(input())

def solve(group, stair_y, stair_x, K):
    members = []
    for y, x in group:
        dist = abs(stair_y - y) + abs(stair_x - x)
        members.append(dist)
    members = deque(sorted(members))
    waiting = deque()
    down_stair = deque()
    time = 0
    while True:
        time += 1
        while down_stair and down_stair[0] <= time:
            down_stair.popleft()
        while members and members[0] <= time:
            members.popleft()
            waiting.append(time)

        if len(down_stair) >= 3:
            continue
        while waiting and waiting[0] + 1 <= time and len(down_stair) < 3:
            waiting.popleft()
            down_stair.append(time + K)


        if len(members) == 0 and len(waiting) == 0 and len(down_stair) == 0:
            break

    return time

def dfs(idx, selected):
    global answer
    if idx == M:
        first_stair = []
        second_stair = []
        for i in range(M):
            if selected[i]:
                first_stair.append(people_list[i])
            else:
                second_stair.append(people_list[i])
        time = max(solve(first_stair, stair_list[0][0], stair_list[0][1], stair_list[0][2]), solve(second_stair, stair_list[1][0], stair_list[1][1], stair_list[1][2]))
        answer = min(answer, time)
        return

    selected[idx] = True
    dfs(idx + 1, selected)
    selected[idx] = False
    dfs(idx + 1, selected)

for tc in range(test_case):
    N = int(input())
    board = [list(map(int, input().split())) for _ in range(N)]
    people_list = []
    stair_list = []
    for y in range(N):
        for x in range(N):
            if board[y][x] == 1:
                people_list.append([y, x])
            elif board[y][x] > 1:
                stair_list.append([y, x, board[y][x]])

    M = len(people_list)
    answer = 987654321
    selected = [False] * M
    dfs(0, selected)

    print("#{} {}".format(tc+1, answer))