[SWEA/Python] 2383. 점심 식사시간

📌 문제

https://swexpertacademy.com/main/main.do

SW Expert Academy

 

📌 문제 접근 방법

1. 처음엔 dp로 풀어야하나 싶어서 아이디어를 짜는 데, 도저히 떠오르지 않았다.
   결국 아이디어를 얻으려고 구글링을 해보니 완전탐색이 가능하다길래 완전탐색으로 풀기로 결정!
2. 입력받은 2차원 배열에서 사람의 위치와 계단의 위치를 찾아서 각각 people과 stairs에 저장해줬다.
3. people은 조합을 이용해서 두 그룹으로 나누었고 첫 번째 그룹과 첫 번째 계단, 두 번째 그룹과 두 번쨰 계단을 각각 go_for_lunch 함수에 넣고 실행해서 둘 중 더 큰 시간을 해당 경우의 수의 시간으로 time에 저장했다.
   (두 그룹 모두 이동을 완료한 시간에 모든 이동이 끝나므로 max 사용)
4. go_for_lunch 함수는 그룹과 계단의 위치를 매개변수로 받는다.
   s에는 각 사람들이 계단에 도착하는 시간을 저장한다.
   e에는 계단을 내려가기 시작한 사람들이 이동을 완료하는 시간을 저장한다.
   time은 현재 시간이고, curr은 현재 계단을 이용중인 사람의 수이다.
5. s에 값이 있다면 아직 이동해야할 사람이 있다는 뜻이므로 while문을 실행한다.
   현재 시간에 이동을 완료한 사람이 있다면, e에서 pop해주고 curr을 1 빼준다.
   현재 시간에 이동을 시작한 사람이 있다면, s에서 pop해주고 e에 이동 완료 시간을 push하고 curr을 1 더해준다.
   (도착하고 1분 후에 이동을 시작하므로 s[0] <= time이 아닌 s[0] < time을 해줬다.)
6. s가 비게 되면 time에 방금 이동을 시작한 사람이 이동을 완료하는 시간을 저장하고 while문을 끝낸다.
7. 위의 과정으로 모든 경우의 수를 확인한 후, 가장 적은 시간을 total에 계속 갱신하여 출력한다.

 

📌 코드

# SWEA 2383 점심 식사시간
from itertools import combinations
from collections import deque

# 두 그룹으로 나누어 내려가는 시간 계산
def go_for_lunch(people, stairs):
    # 계단까지 도착하는 시간
    s = []

    for person in people:
        s.append(abs(person[0]-stairs[0]) + abs(person[1]-stairs[1]))
    
    s = deque(sorted(s))

    # 계단을 내려가서 도착할 시간
    e = deque()

    time = 0
    curr = 0

    while s:
        time += 1

        # 이동을 완료했을 경우
        while e and e[0] == time:
            e.popleft()
            curr -= 1

        while s[0] < time:
            # 계단 이동
            if curr < 3:
                s.popleft()
                if not s:
                    time += grid[stairs[0]][stairs[1]]
                    break

                e.append(time+grid[stairs[0]][stairs[1]])
                curr += 1
            else:
                break
        
    return time


T = int(input())

for t in range(1, T+1):
    N = int(input())
    grid = [list(map(int, input().split())) for _ in range(N)]

    people = []
    stairs = []

    for i in range(N):
        for j in range(N):
            if grid[i][j] == 1:
                people.append((i, j))
            elif grid[i][j] >= 2:
                stairs.append((i, j))
    
    total = float('inf')
    for n in range(N):
        for people1 in combinations(people, n):
            people2 = list(set(people) - set(people1))
            time = max(go_for_lunch(people1, stairs[0]), go_for_lunch(people2, stairs[1]))
            total = min(total, time)
    
    print('#{} {}'.format(t, total))