[소프티어] 좌석관리_히든테케1번 python

 

Bfs와 여러 케이스를 관리해서 적절한 print를 요구하는 문제로 예외케이스 찾기에서 꽤나 머리 아팠던 문제다.

 

import sys

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

seat = [[0] * M for _ in range(N)]
status = {}

dy = [-1, 0, 1, 0]
dx = [0, -1, 0, 1]

def seatDown(id):
    max_safe = -1
    my = -1
    mx = -1
    seat_y = -1
    seat_x = -1
    stop_f = 0
    for i in range(N):
        if stop_f == 1:
            break
        for j in range(M):
            if seat[i][j] == 0:
                if len(status) == 0:
                    my, mx = 0, 0
                    stop_f = 1
                    break
                min_dis = 100000000000000
                cnt = 0
                for key, value in status.items():
                    # 나간 자리에 대해서는 검사하지 않는다.
                    if status[key][2] == 0:
                        cnt += 1
                        y = status[key][0]
                        x = status[key][1]
                        # print("py,px : ", y,x)
                        dist = ((i - y)** 2 + (j - x)** 2)**(1/2)
                        if min_dis > dist:
                            min_dis = dist
                            seat_y = i
                            seat_x = j
                if len(status) != 0 and cnt == 0:
                    my = 0
                    mx = 0
                    break
                if max_safe < min_dis:
                    max_safe = min_dis
                    my = seat_y
                    mx = seat_x
    return my, mx


for i in range(Q):
    op, id = map(str, input().split())
    id = int(id)
    if op == "In":
        if id in status:
            # 1. 현재 좌석에 앉아서 밥을 먹고 있을 경우(0)
            if status[id][2] == 0:
                print(id, "already seated.")
            # 2. 이미 먹고 떠난 경우(1)
            elif status[id][2] == 1:
                print(id, "already ate lunch.")
        else:
            seat_y, seat_x = seatDown(id)
            # 3. 자리가 없는 경우
            if seat_y == -1 and seat_x == -1:
                print("There are no more seats.")
            # 4. 성공적으로 자리에 앉은 경우
            else:
                seat[seat_y][seat_x] = -1
                for i in range(4):
                    ny = seat_y + dy[i]
                    nx = seat_x + dx[i]
                    if 0 <= ny < N and 0 <= nx < M:
                        seat[ny][nx] = -2
                status[id] = [seat_y, seat_x, 0]
                print(id, f"gets the seat ({seat_y + 1}, {seat_x + 1}).")

    elif op == "Out":
        # 1. 아직 점심을 못먹었다. - status에 해당 Id가 없는 경우
        if id not in status:
            print(id, "didn't eat lunch.")
        # 2. 이미 밥을 먹고 난 후 - status에 1
        else:
            if status[id][2] == 1:
                print(id, "already left seat.")
            # 3. (x,y)에 앉아있는 경우
            elif status[id][2] == 0:
                sy = status[id][0]
                sx = status[id][1]
                print(id, f"leaves from the seat ({sy + 1}, {sx + 1}).")
                status[id][2] = 1
                seat[sy][sx] = 0
                for i in range(4):
                    ny = sy + dy[i]
                    nx = sx + dx[i]
                    if 0 <= ny < N and 0 <= nx < M:
                        if seat[ny][nx] != 0:
                            flag = 0
                            for j in range(4):
                                nny = ny + dy[j]
                                nnx = nx + dx[j]
                                if 0 <= nny < N and 0 <= nnx < M:
                                    if seat[nny][nnx] == -1:
                                        seat[ny][nx] = -2
                                        flag = 1
                                    elif flag == 0:
                                        seat[ny][nx] = 0

 

 

나를 괴롭혔던 예외 케이스는 1번이였다.

일반적으로 hidden test case는 가장 작은 입력값에 대한 경우을 의미하므로 내가 실험해본 값은 아래와 같다.

 

1 1 3

In 1

Out 1

In 2

 

이 예제를 실행했을 때 Out까지는 잘 실행되었으나 기존의 코드로 동작하도록 하면 자리에 앉은 사람이 아무도 없어서 안전도를 구하지 못해 앉을 수 있는 자리가 없는것으로 잘못 이해하고 코드가 동작하는 오류가 있었다.

따라서 이걸 해결하기 위해서 cnt 값을 이용해서 안전도를 구한 횟수가 0이라면 자리가 모두 비어서 못구하는 것이므로 무조건 (1,1) 자리에 앉는 것으로 코드를 수정하여 문제를 해결할 수 있었다.

 

이 문제를 통해서 배운 점으로는 다른 채점 프로그램에서 오답이 뜨는 경우에 직접 테스트 케이스를 만들어봐야하는데

우선적으로 가장 작은 입력값이 주어지는 경우에 대해서 테스트해보면 의외로 이때 문제가 가장 많이 발생할 수 있다는 것이다.