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

Level 3가 되더니 확실히 난이도가 올라갔다. 푸는데 생각보다 많은 시간이 소요된 문제였다.

다만 몇몇 아이디어들은 계속해서 사용되는 형식이라 중요한 문제이다.(상하좌우 확인)

문제 

https://softeer.ai/practice/6267

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

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

현재 K개의 좌석이 차 있고, 이 중 i번째 좌석은 (xi,yi)라고 하자. 이 상황에서 어떤 좌석 (X,Y)의 안전도 D는 유클리디안 거리의 최소값이다.

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

기항이는 현재 비어있는 좌석 (X,Y) 중에서 방역 수칙을 고려하는 동시에, 안전도가 가장 높은 좌석을 새로 들어오는 사람에게 배정해준다.
배정해줄수 있는 좌석 중 안전도가 가장 높은 좌석이 여럿 있을 수 있다. 이 때는 그 중에서 X가 가장 낮은 좌석을, X도 같다면 Y가 가장 낮은 좌석을 배정해 준다. 특수하게, 현재 모든 좌석이 비어있다면 (1,1)이 배정된다.
사번이 id인 어떤 사원이 식당에서 떠난다면, 그 사원이 있던 자리는 빈 자리가 된다. 각 사원들에게 주어지는 점심 식사는 단 한번이므로, 여러 번 점심을 먹을 수는 없다. 그러므로 이미 점심을 먹은 사원은 돌려보내야 한다.
이외에도 각 직원의 점심 식사 여부에 따른 처리가 요구되는데, 출력 형식을 참고하여 모든 작업을 적절히 처리해보자.

 

주의사항

2차원 배열 선언에 확인해야할 내용들이 있었다. 기본적이지만 실수하기 쉬운 부분이다. 

https://blog.sysbot32.com/entry/Python-2%EC%B0%A8%EC%9B%90-%EB%B0%B0%EC%97%B4-%EC%84%A0%EC%96%B8%ED%95%98%EA%B8%B0

[Python] 2차원 배열 선언하기

 

풀이 & 아이디어

각 부분을 적절히 처리하는 코드를 작성했다. 

우선, 각 dictornary에 필요한 정보인 seated, ate, seat_pos 3가지 정보를 tuple()로 묶어서 각 user id의 value로 준다. 

이후 정보들을 위해 아래의 아래의 기능을 하는 함수들을 작성한다. 

1. Eucidian 거리를 정의

2. 바로 인접한 거리에 사람들이 있는지 확인

3. 안전도가 높은 좌석을 확인 

N, M, Q = map(int, input().split())

# 현재 좌석 배정 상태 (0이면 빈 자리, 1이면 차 있는 자리)
seat_array = [[0 for _ in range(M)] for _ in range(N)]

# 사원의 상태를 기록하는 딕셔너리
# 'seated': 현재 앉아 있는지 여부, 'ate': 이미 점심을 먹었는지 여부, 'seat_pos': 앉아있는 좌석의 위치
check_id = {}

# 유클리디언 거리 계산
def euc_dist(x1, y1, x2, y2):
    return ((x1 - x2)**2 + (y1 - y2)**2)**0.5

# 상하좌우 인접 좌석을 확인하는 함수
def is_adjacent_safe(x, y):
    # 좌표가 유효한 범위 내에 있는지 확인하는 함수
    def in_bounds(nx, ny):
        return 0 <= nx < N and 0 <= ny < M
    
    # 상하좌우 4방향 확인 (위, 아래, 왼쪽, 오른쪽)
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    for dx, dy in directions:
        nx, ny = x + dx, y + dy
        if in_bounds(nx, ny) and seat_array[nx][ny] == 1:
            return False  # 인접한 곳에 사람이 있으면 False
    return True  # 상하좌우에 아무도 없으면 True

# 안전도가 가장 높은 좌석을 찾는 함수
def find_best_seat():
    empty_seats = []
    
    for i in range(N):
        for j in range(M):
            if seat_array[i][j] == 0 and is_adjacent_safe(i, j):  # 빈 좌석이고 방역 수칙을 만족하면
                min_distance = float(max(N+100,M+100))
                # 모든 차 있는 좌석과의 거리 중 최소값을 찾는다
                for x in range(N):
                    for y in range(M):
                        if seat_array[x][y] == 1:
                            min_distance = min(min_distance, euc_dist(i, j, x, y))
                empty_seats.append((min_distance, i + 1, j + 1))  # 좌석 번호는 1부터 시작이므로 +1
                
    if not empty_seats:
        return None  # 빈 좌석이 없거나 방역 수칙을 만족하는 좌석이 없다면 None 반환
    
    # 안전도가 가장 높은 좌석을 찾고, X, Y 좌표 순으로 정렬
    empty_seats.sort(key=lambda x: (-x[0], x[1], x[2]))
    return empty_seats[0][1], empty_seats[0][2]  # 가장 좋은 좌석의 (X, Y) 반환

# 명령어 처리
for _ in range(Q):
    order, emp_id = input().split()
    emp_id = int(emp_id)
    
    # 사원이 In 명령을 받은 경우
    if order == 'In':
        if emp_id in check_id:
            if check_id[emp_id]['ate']:
                print(f"{emp_id} already ate lunch.")
            elif check_id[emp_id]['seated']:
                print(f"{emp_id} already seated.")
        else:
            # 빈 좌석을 찾기
            seat = find_best_seat()
            if seat is None:
                print("There are no more seats.")
            else:
                x, y = seat
                seat_array[x-1][y-1] = 1  # 좌석 배정
                check_id[emp_id] = {'seated': True, 'ate': False, 'seat_pos': (x, y)}  # 사원의 상태 업데이트
                print(f"{emp_id} gets the seat ({x}, {y}).")
    
    # 사원이 Out 명령을 받은 경우
    elif order == 'Out':
        if emp_id not in check_id:
            print(f"{emp_id} didn't eat lunch.")
        elif check_id[emp_id]['ate']:
            print(f"{emp_id} already left seat.")
        elif check_id[emp_id]['seated']:
            # 사원이 앉아 있는 좌석에서 떠남
            x, y = check_id[emp_id]['seat_pos']  # 사원이 앉아있던 좌석 위치를 가져옴
            seat_array[x-1][y-1] = 0  # 좌석을 비움
            check_id[emp_id]['seated'] = False
            check_id[emp_id]['ate'] = True
            print(f"{emp_id} leaves from the seat ({x}, {y}).")