점심 식사시간 Python(SW Expert Academy, SWEA)

난이도 : 모의 SW 역량테스트

문제번호 : 2383

문제 주소 및 출처입니다.

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

SW Expert Academy

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

---

1. 문제 설명

N*N 크기의 정사각형 모양의 방에 사람들이 앉아 있다. 점심을 먹기 위해 아래 층으로 내려가야 하는데, 밥을 빨리 먹기 위해 최대한 빠른 시간 내에 내려가야 한다. 방 안의 사람들은 P로, 계단 입구를 S라고 했을 때 [Fig. 1]은 사람의 위치와 계단 입구의 위치를 표시한 모습이다. 이동 완료 시간은 모든 사람들이 계단을 내려가 아래 층으로 이동을 완료한 시간이다. 사람들이 아래층으로 이동하는 시간은 계단 입구까지 이동 시간과 계단을 내려가는 시간이 포함된다. ① 계단 입구까지 이동 시간         - 사람이 현재 위치에서 계단의 입구까지 이동하는데 걸리는 시간으로 다음과 같이 계산한다.         - 이동 시간(분) = | PR - SR | + | PC - SC |           (PR, PC : 사람 P의 세로위치, 가로위치, SR, SC : 계단 입구 S의 세로위치, 가로위치)     ② 계단을 내려가는 시간         - 계단을 내려가는 시간은 계단 입구에 도착한 후부터 계단을 완전히 내려갈 때까지의 시간이다.         - 계단 입구에 도착하면, 1분 후 아래칸으로 내려 갈 수 있다.         - 계단 위에는 동시에 최대 3명까지만 올라가 있을 수 있다.         - 이미 계단을 3명이 내려가고 있는 경우, 그 중 한 명이 계단을 완전히 내려갈 때까지 계단 입구에서 대기해야 한다.         - 계단마다 길이 K가 주어지며, 계단에 올라간 후 완전히 내려가는데 K 분이 걸린다. 사람의 위치와 계단 입구의 위치 및 계단의 길이 정보가 표시된 N*N 크기의 지도가 주어진다. 이때, 모든 사람들이 계단을 내려가 이동이 완료되는 시간이 최소가 되는 경우를 찾고, 그 때의 소요시간을 출력하는 프로그램을 작성하라.

 

예시

방의 한 변의 길이 N 이 5인 지도가 [Fig. 2]와 같이 주어진 경우를 생각해보자. 지도 내에 1 은 사람을 나타내고, 2 이상 10 이하의 숫자는 계단의 입구를 나타내며 해당 숫자는 계단의 길이를 의미한다. [Fig. 2]에는 사람 6명이 있고, 계단은 2개가 있으며 길이는 각각 3과 5이다. 다음은 이동 완료되는 시간이 최소가 되는 경우 중 하나이다.     - 1번, 2번, 3번 사람은 길이가 3인 1번 계단을 통해 이동     - 4번, 5번, 6번 사람은 길이가 5인 2번 계단을 통해 이동 이 경우, 모든 사람이 계단을 내려가 이동 완료하는 최소 시간은 9분이다. 다른 예시로, 한 변의 길이가 N인 방에 [Fig. 3]과 같이 배치되어 있는 경우를 생각해보자. 지도 내에 1 은 사람을 나타내고, 2 이상 10 이하의 숫자는 계단의 입구를 나타내며 해당 숫자는 계단의 길이를 의미한다. 다음은 이동이 완료되는 시간이 최소가 되는 경우 중 하나이다.     - 1번, 2번, 3번, 4번 사람은 길이가 2인 1번 계단을 통해 이동     - 5번, 6번 사람은 길이가 5인 2번 계단을 통해 이동 이 경우, 모든 사람이 계단을 내려가 이동 완료하는 최소 시간은 8분이다.

 

제한사항

1. 시간제한 : 최대 50개 테스트 케이스를 모두 통과하는데, C/C++/Java 모두 3초 2. 방의 한 변의 길이 N은 4 이상 10 이하의 정수이다. (4 ≤ N ≤ 10) 3. 사람의 수는 1 이상 10 이하의 정수이다. (1 ≤ 사람의 수 ≤ 10) 4. 계단의 입구는 반드시 2개이며, 서로 위치가 겹치지 않는다. 5. 계단의 길이는 2 이상 10 이하의 정수이다. (2 ≤ 계단의 길이 ≤ 10) 6. 초기에 입력으로 주어지는 사람의 위치와 계단 입구의 위치는 서로 겹치지 않는다.

 

입력

입력의 맨 첫 줄에는 총 테스트 케이스의 개수 T가 주어지고, 그 다음 줄부터 T개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 방의 한 변의 길이 N이 주어진다. 다음 N줄에는 N*N 크기의 지도의 정보가 주어진다. 지도에서 1은 사람을, 2 이상은 계단의 입구를 나타내며 그 값은 계단의 길이를 의미한다.

출력

테스트 케이스의 개수만큼 T줄에 T개의 테스트 케이스 각각에 대한 답을 출력한다. 각 줄은 "#x"로 시작하고 공백을 하나 둔 다음 정답을 출력한다. (x는 1부터 시작하는 테스트 케이스의 번호이다) 정답은 이동이 완료되는 최소의 시간을 출력한다.

예시

입력	출력
10 5 0 1 1 0 0 0 0 1 0 3 0 1 0 1 0 0 0 0 0 0 1 0 5 0 0 5 0 0 1 1 0 0 0 1 0 2 0 0 0 1 0 0 1 0 0 0 1 0 5 0 0 …	#1 9 #2 8 #3 9 #4 7 #5 8 #6 8 #7 11 #8 11 #9 18 #10 12

---

2. 문제풀이

사람의 수가 10명 이하이기 때문에 완전탐색으로 풀 수 있다고 판단했다. 데이터를 받으면 사람과 계단의 거리를 계산하여 따로 저장했다. DFS를 이용하여 각각의 사람이 1번계단과 2번계단으로 가는 모든 경우의 수로 판단하여 계산했다. 이후 계단마다 걸리는 시간을 각각 계산했다. 계산은 이동거리를 줄이거나, 계단을 내려가거나, 대기하는 경우를 나누어 계산했다. 2그룹으로 분리하여 계단으로 보냈을때 시간이 오래걸리는 계단을 저장하여 제일 짧은 시간을 측정했다.

---

3. 소스코드

#SW 역량테스트 2383 점심 식사시간
def Calculation(stair_list, stair):
    count, d_count = 0, 0
    delete_queue = []
    #이동중인사람이나 대기중인사람, 내려가는 사람이있다면 반복
    while stair_list or delete_queue or d_count:
        #대기하는 사람이 있다면
        while d_count:
            #최대인원이 다찼다면 정지
            if len(delete_queue) == 3:
                break
            #내려가는 사람들에게 넣어주기
            delete_queue.append(stair[2])
            #한명 넣을때마다 대기인원 감소
            d_count -= 1
 
        #내려가는 인원이 있을때 동작
        for i in range(len(delete_queue)-1, -1, -1):
            #시간을 감소시키고
            delete_queue[i] -= 1
            #전부 내려갔다면 뺀다
            if delete_queue[i] <= 0:
                delete_queue.pop(i)
        
        #이동중인 사람이 있다면
        for i in range(len(stair_list)-1, -1, -1):
            #거리를 감소키고
            stair_list[i] -= 1
            #계단까지 갔다면
            if stair_list[i] <= 0:
                #빼버리고 대기인원 증가
                stair_list.pop(i)
                d_count += 1
        #1초 증가
        count+=1
    return count
 
#조합찾기
def dfs(idx):
    #조합이 결정되었다면
    if idx == Num:
        global min_count
        stair_list1, stair_list2 = [], []
        #1번계단, 2번계단 분리하기
        for i in range(Num):
            if check[i]: stair_list1.append(Peoples[i][0])
            else : stair_list2.append(Peoples[i][1])
        #시간계산하기, 두계단중 가장 긴시간을 가져온다.
        count = max(Calculation(sorted(stair_list1), Stairs[0]), Calculation(sorted(stair_list2), Stairs[1]))
        #제일 작은 시간으로 교체
        min_count = min(count, min_count)
        return
    check[idx] = False
    dfs(idx+1)
    check[idx] = True
    dfs(idx+1)
    
 
T = int(input())
for t in range(1, T+1):
    N = int(input())
    #지도 표시
    map_list = [list(map(int, input().split())) for _ in range(N)]
    #사람위치, 계단위치, 계단값
    Peoples, Stairs = [], []
    #사람수, 리턴할 시간
    Num, min_count = 0, 987654321
    for i in range(N):
        for j in range(N):
            temp_num = map_list[i][j]
            if temp_num:
                #사람이면 사람수추가하고 위치추가
                if temp_num == 1:
                    Num += 1
                    Peoples.append([i, j])
                #계단이라면 계단위치 추가하고 계단길이 추가
                else:
                    Stairs.append([i, j, temp_num])
    #사람의 계단마다 거리계산
    for i in range(len(Peoples)):
        distance1 = abs(Peoples[i][0] - Stairs[0][0]) + abs(Peoples[i][1] - Stairs[0][1])
        distance2 = abs(Peoples[i][0] - Stairs[1][0]) + abs(Peoples[i][1] - Stairs[1][1])
        Peoples[i][0] = distance1
        Peoples[i][1] = distance2
    #1번 계단으로 갈것인지, 2번계단으로 갈것인지
    check = [False for _ in range(Num)]
    #모든 경우의수 찾으러 가자
    dfs(0)
    print('#{} {}'.format(t, min_count+1))