[Softeer] 21년 재직자 대회 예선 - 좌석 관리(파이썬)

☑️문제 링크 

https://softeer.ai/practice/6267

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

☑️문제 소개

오늘 일은 사람들이 사회적 거리 두기를 잘 지키면서 식당 좌석에 앉도록 상황을 관리하는 일이다.

현재 식당에는 좌석 N×M개가 N행 M열로 나열되어 있는데, 각 좌석에는 (1,1)에서 (N, M)로 좌표가 배정되어 있다. x행 y열에 있는 좌석의 좌표는 (x, y)이다.

점심시간에는 많은 사람들이 식당을 드나든다. 사번이 id인 어떤 사원이 식당에 왔다면, 다음 조건에 맞춰 이 사원을 위한 좌석을 배정해 준다.

현재 K개의 좌석이 차 있고, 이 중 i번째 좌석은 (xi, yi)라고i,yi 하자. 이 상황에서 어떤 좌석 (X, Y)의 안전도 DX, Y는 

이다.

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

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

☑️ 세부 조건

1. 작업이 In {id}로 주어졌을 때

- 사번이 id인 사원이 현재 좌석에 앉아 밥을 먹고 있다면, {id} already seated.를 출력한다.

- 사번이 id인 사원이 이미 밥을 먹고 떠났다면, {id} already ate lunch.를 출력한다.

- 사번이 id인 사원이 자리가 가득 차서 좌석을 배정받는 데 실패했다면, There are no more seats.를 출력한다.

- 사번이 id인 사원이 성공적으로 좌석 (x,y)에 앉았다면, {id} gets the seat ({x}, {y}).를 출력한다.

    2. 작업이 Out {id}로 주어졌을 때

 

- 사번이 id인 사원이 아직 점심을 먹지 못했다면, {id} didn't eat lunch.를 출력한다.

- 사번이 id인 사원이 이미 밥을 먹고 좌석을 떠났다면, {id} already left seat.를 출력한다.

- 사번이 id인 사원이 좌석 (x, y)에 앉아 있었다면, {id} leaves from the seat ({x}, {y}). 를 출력한다. 이 사원은 점심을 먹은 상태로 기록된다.

 

☑️문제풀이

가장 먼저 떠오른 것은 배열을 만들어 0으로 채워 넣어야겠다는 것이었다. 그리고 앉은 자리에는 다른 수를 넣어 처리해보기로 했다.

사원에 대한 것은 딕셔너리로 만들어 한번에 처리하자. 각 id에 앉은 좌석의 좌표와 밥을 먹었는지 아닌지에 대한 정보를 넣는다.

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

그리고 사용할 함수들을 생각해보았다

- 상하좌우에는 앉을 수 없기 때문에 guard_check라는 함수를 이용해 상하좌우에도 0으로 채워주자.

- type는 1과 -1로 나갔을 때 그 자리의 상하좌우를 비워주기도 해야 하니까 함수의 인자로 사용했다.

def guard_check(x, y, type):
    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

 

다음은 IN OUT에 따른 동작들에 대한 코드이다. 

- 배열은 0,0부터 시작하므로 출력할 때는 x, y에 +1 씩 해서 출력해 주면 된다.

- 앉았으면 guard_check를 이용해 (type = -1) 주위를 -1로 만들어준다. 그리고 딕셔너리에 정보를 저장해 준다.

- 떠났을 때 ate를 True로 해주고 guard_check의 tpye를 1로 해서 다시 주변을 0으로 만들어준다.

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.")

 

대망의 calculate_safety 함수!!

- 로직을 이해하는데 꽤나 오랜 시간이 걸렸지만, 그럴 때일수록 단순하게 생각하자.

1. 모든 경우의 수를 고려해야 하니까 + 안전도가 같을 경우 x,y가 작은순으로 해야하니까 x, y의 이중 for문을 이용하자.
2. 새로운 사람을 앉힐 자리에서 가장 가까운 사람을 찾아 거리를 계산하자. (= distance)
3. 그 거리가 가장 큰 자리를 찾자.( = safety)

이 3가지를 이용한 코드

- d에 가장 가까운 거리를 저장하고 safety와 비교해서 가장 큰 d값을 갖는 x, y를 찾아주는 것이다.

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)
                        if d > distance:
                            d = distance
                if safety < d:
                    tx, ty = x, y
                    safety = d

    if map[tx][ty] != 0:
        return "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})."

 

☑️전체 코드

import sys

def guard_check(x, y, type):
    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)
                        if d > distance:
                            d = distance
                if safety < d:
                    tx, ty = x, y
                    safety = d

    if map[tx][ty] != 0:
        return "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.")