[Algorithm] Softeer [21년 재직자 대회 예선] 좌석관리 (python)

[ Softeer 연습문제 - 좌석관리 ]

Softeer - 현대자동차그룹 SW인재확보플랫폼

• 문제명 : 좌석관리 [21년 재직자 대회 예선]
• 사용언어 : python

---

  문제

현대자동차그룹에서 사내 식당 매니저로 일하는 기항이는 점심시간에 맞춰 일을 하고 있다. 오늘 일은 사람들이 사회적 거리 두기를 잘 지키면서 식당 좌석에 앉도록 상황을 관리하는 일이다.
현재 식당에는 좌석 N×M개가 N행 M열로 나열되어 있는데, 각 좌석에는 (1,1)에서 (N,M)로 좌표가 배정되어 있다. x행 y열에 있는 좌석의 좌표는 (x, y)이다.
점심시간에는 많은 사람들이 식당을 드나든다. 사번이 id인 어떤 사원이 식당에 왔다면, 다음 조건에 맞춰 이 사원을 위한 좌석을 배정해 준다.
현재 K개의 좌석이 차 있고, 이 중 i번째 좌석은 (xi,yi)라고 하자. 이 상황에서 어떤 좌석 (X,Y)의 안전도 DX, Y는

이다.
즉, 다른 사람까지의 거리 중 가장 가까운 거리다. 단, 방역 수칙에 따르면 사람들은 상하좌우에 바로 붙어 앉을 수 없다.

또한 아래의 그림에서 처럼 경계 밖은(좌, 하) 고려하지 않는다.

기항이는 현재 비어있는 좌석 (X,Y) 중에서 방역 수칙을 고려하는 동시에, 안전도가 가장 높은 좌석을 새로 들어오는 사람에게 배정해 준다.

배정해 줄 수 있는 좌석 중 안전도가 가장 높은 좌석이 여럿 있을 수 있다. 이 때는 그중에서 X가 가장 낮은 좌석을, X도 같다면 Y가 가장 낮은 좌석을 배정해 준다. 특수하게, 현재 모든 좌석이 비어있다면 (1,1)이 배정된다.

사번이 id인 어떤 사원이 식당에서 떠난다면, 그 사원이 있던 자리는 빈자리가 된다. 각 사원들에게 주어지는 점심 식사는 단 한 번이므로, 여러 번 점심을 먹을 수는 없다. 그러므로 이미 점심을 먹은 사원은 돌려보내야 한다.

이외에도 각 직원의 점심 식사 여부에 따른 처리가 요구되는데, 출력 형식을 참고하여 모든 작업을 적절히 처리해 보자.

 

 

 

  알고리즘 및 풀이

→ 제일 가까운 거리에서 안전도가 높은 자리를 찾기 !

라는데 나는 처음에 왜 제일 가까운 거리의 자리에서 찾는지가 이해가 안 되었다. 가장 먼 곳이 안전도가 높을 텐데...

이 문제에 더 이상 뺏길 시간이 없는데..!! 코드 풀이는 이해가 되는데 문제가 말하는 게 '제일 가까운 거리'에서 안전도가 높은 자리를 찾는 게 이해가 안 된다..........

 

시간을 좀 가져보고 다시금 접근해 본 결과 '안전도'를 구하기 위해서는 제일 가까운 거리의 자리와 계산을 해야 돼서 '제일 가까운 거리'에서 안전도가 높은 자리를 찾는 거였다.. 그냥 문제는 이렇게 이해하고 넘어가자... 

 

import sys

def guard_check(x, y, type):
	# 사회적 거리를 위해 상,하,좌,우에 가드 역할을 하는 값들을 더하고 뺌.
    # in -> -1 씩
    # out -> +1 씩
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < N and 0 <= ny < M:
            map[nx][ny] += type

    
def calculate_safety(id):
    tx = ty = safety = 0
    # 모든 좌석에 대해 탐색
    for x in range(N):
        for y in range(M):
            d = sys.maxsize
            # 빈 좌석일 경우에만 계산
            if map[x][y] == 0:
                for xi, yi, ate in employee.values():
                    if ate: continue
                    else:
                        distance = ((xi - x) ** 2 + (yi - y) ** 2 ) ** 1/2
                        if d > distance:
                            d = distance
                if safety < d:
                    tx, ty = x, y
                    safety = d

    if map[tx][ty] != 0:
        return f"There are no more seats."  
        
    # 좌석 할당 및 가드 역할 값 조정
    employee[id] = (tx, ty, False)
    map[tx][ty] = id
    guard_check(tx, ty, -1)
    return f"{id} gets the seat ({tx+1}, {ty+1})."


# 입력 받기
N, M, Q = map(int, input().split())
map = [[0] * M for _ in range(N)]
employee = {}        # {id:(x,y,ate)...}   ate = True/False

for _ in range(Q):
    work, id = input().split()
    if work == "Out":
        if id not in employee:
            print(f"{id} didn't eat lunch.")
        else:
            x, y, ate = employee[id]
            if ate:
                print(f"{id} already left seat.")
            else:
                print(f"{id} leaves from the seat ({x+1}, {y+1}).")
                guard_check(x, y, 1)
                map[x][y] = 0
                employee[id] = (x, y, True)
    else:
        if id not in employee:
            # 첫방문
            print(calculate_safety(id))
        else:
            x, y, ate = employee[id]
            if ate:
                print(f"{id} already ate lunch.")
            else:
                print(f"{id} already seated.")

 

 

 

드디어... 성공했다................. ㅠ_ㅠ

 

작업을 처리할 때 print 되는 문구의 오차들로도 코드실행이 제대로 안되니 유의해서 정답을 작성해야 된다 !

또한 Out 을 처음에 OUT으로 처리했다가도 오류가 났었다.