SWEA 2383번. 점심 식사시간

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5-BEE6AK0DFAVl&

 

 

코드는 

https://github.com/ChangmoKang/problem_solving/blob/master/SWEA/2383.py#L74

이 분 코드를 참고했음.

 

 

1. 사람이 계단을 선택한다고 생각하지말고, 사람은 여러 명, 계단은 항상 2개이므로 계단이 사람을 선택한다고 생각한다. -> DFS가 됨

2. 계단이라고 해서 큐처럼 진짜 한 칸씩 땡겨오려고 하지 말고, 0이 되면 그 자리에 대기자를 넣는다고 생각을 하자. 

3. 사람들을 어떻게 구별하나 고민하지 말고, 여기서 필요한 정보는 각 사람~계단까지의 거리 뿐임을 기억하자. 중복되도 상관없다. 리스트에 거리만 계산해서 넣으면 끝이다. 

4. 괜히 괜히 괜히 엄청나게 복잡하고 어려운 것 같으면 뭔가 이상하다는 뜻이다. 더 쉬울만한 다른 방법을 생각해보자.

import sys


def init():
    for i in range(n):
        for j in range(n):
            if board[i][j] == 1:
                people.append([i, j])
            elif board[i][j] != 0:  # 1도 아니고 0도 아니면 계단
                stair.append([i, j, board[i][j]])


def calc_distance(pdx, sdx):
    return abs(people[pdx][0] - stair[sdx][0]) + \
            abs(people[pdx][1] - stair[sdx][1])


def start(count, choice):
    global min_time
    if count == people_num:
        wait = [[], []]
        on_stair = [[0, 0, 0], [0, 0, 0]]

        for pdx in range(people_num):  # pdx = people index
            wait[choice[pdx]].append(calc_distance(pdx, choice[pdx]))  # 거리를 대기자 리스트에 넣는다

        wait[0].sort()
        wait[1].sort()

        # 계단1,2 합쳐서 가장 먼저 도착하는 사람을 시작 시간(t)으로 놓는다.
        if wait[0] and wait[1]:
            t = min(wait[0][0], wait[1][0])
        elif wait[0] and not wait[1]:
            t = wait[0][0]
        else:
            t = wait[1][0]

        while wait[0] or wait[1]:  # 대기자가 있을 때까지 반복
            for sdx in range(2):  # sdx = stair index
                for floor in range(3):  # 매번 각 계단의 *세 자리*를 살펴서 
                    if on_stair[sdx][floor] > 0:  # 계단에 누가 있으면
                        on_stair[sdx][floor] -= 1  # 한 층 내려오게 하고
                    if on_stair[sdx][floor] == 0:  # 0이 되면 (=빈 자리가 생김)
                        if wait[sdx] and wait[sdx][0] < t:  # 해당 계단에 대기자가 있고 & 도착할 시간이 지났으면
                            on_stair[sdx][floor] = stair[sdx][H]  # 해당 계단의 높이를 리스트에 넣는다
                            wait[sdx].pop(0)
            t += 1

        t += max(max(on_stair[0]), max(on_stair[1])) - 1
        min_time = min(t, min_time)
        return
    
    else:  # DFS로 순열 찾기 (count == 사람숫자 될 때마다 본격적인 시뮬레이션 시작)
        for i in range(2):
            start(count+1, choice + [i])


if __name__ == '__main__':
    H = 2
    input = sys.stdin.readline
    T = int(input())
    for t in range(T):
        n = int(input())
        min_time = 9999
        board = [list(map(int, input().split())) for _ in range(n)]
        people, stair = [], []
        init()
        people_num = len(people)

        start(0, [])
        print("#{}".format(t+1), min_time)