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

문제

<배경>

 

---

<입력>

---

<출력>

 

---

<예시>

---

풀이

이전 두 문제에 비해 꽤 복잡해졌다.

 

<ID리스트>

사용의 편의를 위해 0번 인덱스는 버리고 id의 최댓값보다 1큰 10001길이를 갖는 ID라는 리스트를 만들자.

먼저 각 사람(id)이 가질 수 있는 상태는 밥을 먹기 전, 밥을 먹는 중, 밥을 먹고 난 후 세 가지가 있다.

각 상태에 대해 0, [x,y], 1라는 값이 ID리스트에 들어있다고 하자.

즉 사번이 5인 사원이 현재 (2,3)자리에서 밥을 먹고 있다면 ID[5] = [2,3] 이 되는 것이다.

 

<경우 나누기>

입력으로 In이 주어졌을 때 가능한 동작은 아래와 같다.

1. 아직 밥을 먹지 않은 사람일 때
   1. 앉을 수 있는 자리가 있을 때
   2. 앉을 수 있는 자리가  없을 때
2. 이미 밥을 먹은 사람일 때
3. 밥을 먹고 있을 때

입력으로 Out이 주어졌을 때 가능한 동작은 아래와 같다.

1. 아직 밥을 먹지 않은 사람일 때
2. 이미 밥을 먹은 사람일 때
3. 밥을 먹고 있는 사람일 때

각각의 경우에 대해 대부분 문제에서 요구하는 내용을 print하면 된다.

다만 자리에 착석하거나 있던 자리에서 나올 때는 table리스트와 ID리스트의 값을 바꿔줘야한다.

코드는 아래와 같다.

n,m,q = map(int,input().split())
ID = [0]*(10000+1) #0 : not in , 1: out, [x,y]
table = [[0]*(n+2) for _ in range(n+2)] 

for i in range(q):
    inout, pid = input().split()
    pid = int(pid)
    if inout == "In":
        if ID[pid]==0:
            if assgin(pid):
                print(f'{pid} gets the seat ({ID[pid][0]},{ID[pid][1]}).')
            else:
                print('There are no more seats.')
        elif ID[pid]==1:
            print(f'{pid} already ate lunch.')
        else:
            print(f'{pid} already seated.')
    elif inout == "Out":
        if ID[pid]==0:
            print(f'{pid} didn\'t eat lunch.')
        elif ID[pid]==1:
            print(f'{pid} already left seat.')
        else:
            print(f'{pid} leaves from the seat ({ID[pid][0]},{ID[pid][1]}).')
            table[ID[pid][0]][ID[pid][1]] = 0
            ID[pid] = 1

 

 

<assign함수>

1-1, 1-2 경우에서 쓰이는 앉을 수 있는자리가 있는지 판단하고 그 자리에 사람을 할당하는 함수가 필요하다.

위 코드에서는 이런 기능을 수행하는 assign()함수가 있다고 생각하고 코드를 구현했다.

 

배정 시에는 가장 가까운 사람과 거리(안전도)가 가장 먼 좌석을 배정해줘야한다.

추가로 당연히 어떤 사람에게 자리를 주려면 그 주변 자리와 해당 자리가 비어있어야한다.

따라서 자신과 주변이 비어있는 좌석들에 대해 안전도를 구한 후 그 중 최댓값일 때의 자리좌표를 ID[해당사번]의 값으로 해준다.

 

<nearest함수>

이 함수는 특정 자리에 대해 안전도를 찾는 함수이다.

모든 자리를 돌며 가장 가까운 거리를 구한다.

거리 값 자체를 사용하지는 않고 비교를 위해서만 사용되므로 루트를 씌우지 않았다.

def nearest(x,y):
    minD = 1000
    for i in range(1,n+1):
        for j in range(1,m+1):
            if (table[i][j]):
                d = (x-i)*(x-i) + (y-j)*(y-j)
                if d < minD:
                    minD = d
    return minD

def assign(pid):
    maxD = 0
    for i in range(1,n+1):
        for j in range(1,m+1):
            if table[i][j] == 0 and table[i-1][j] == 0 and table[i][j-1] == 0 and table[i+1][j] == 0 and table[i][j+1] == 0:
                d = nearest(i,j)
                if d>maxD:
                    maxD = d
                    ID[pid] = [i,j]
    if maxD == 0:
        return False
    else:
        table[ID[pid][0]][ID[pid][1]] = 1
        return True

 

이제 이 두 코드 덩어리를 합치면 문제를 해결할 수 있다.