아직 계정이 없으신가요? 회원가입

Dev. Talk

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

회원사진gbh5854
209 views2021-11-29 20:40

아래 코드를 제출한 후 상세보기를 보니까 모든 테케가 오답인데요.


반례 알려주시면 감사하겠습니다.


혹시 제가 출력을 잘못하고 있는건가요?


import sys

N,M,Q = input().split(' ')
N = int(N)
M = int(M)
Q = int(Q)
in_queue = []
in_dict = {}
out_queue = []
dx = [-1,1,0,0]
dy = [0,0,-1,1]

def print_map():
	for i in map:
		print(i)

def cal_seat(user_id):
	max_safe = 0
	max_x = 0
	max_y = 0
	no_seat = True

	for i in range(N):
		for j in range(M):
			if map[i][j] == 0:
				flag = False
				for tmp in range(4):
					nx = i+dx[tmp]
					ny = j+dy[tmp]
					if nx >= 0 and nx < N and ny >= 0 and ny < M:
						if map[nx][ny] != 0:			#상하좌우 사람 x
							flag = True
							break
				if flag == False:
					no_seat = False
					min_safe = 1000
					# print(in_dict)
					for point in in_queue:
						tar_x, tar_y = in_dict[point][0], in_dict[point][1]
						# print(tar_x, tar_y)
						distance = ((i-tar_x)**2 + (j-tar_y)**2)**(1/2)
						# print("(", i, ", ", j, ")" , "(", tar_x, ", ", tar_y,  ")")
						# print("distance = ", distance)
						if distance < min_safe:
							min_safe = distance
					if max_safe < min_safe:
						max_safe = min_safe
						max_x = i
						max_y = j
	if no_seat == True:
		print("There are no more seats.", end='\n')
	else:
		map[max_x][max_y] = user_id
		in_queue.append(user_id)
		in_dict[user_id] = [max_x, max_y]
		print(user_id, "gets the seat ("+ str(max_x+1)+ ", "+ str(max_y+1)+ ").")
	# print_map()

# print()	


map = [[0 for i in range(M)] for j in range(N)]

# if 1 not in map:
# 	print('empty')
for work in range(Q):
	where, user_id = input().split(' ')
	# print(where, user_id)
	user_id = int(user_id)

	if where == "In":
		if len(in_queue) == 0: #map empty
			map[0][0] = user_id
			in_queue.append(user_id)
			in_dict[user_id] = [0,0]
			print(user_id,"gets the seat (1, 1).")
		else:
			tmp = False
			for i in map:
				if user_id in i:
					tmp = True
					print(user_id, "already seated.")
					break
			if tmp == True:
				continue

			if user_id in out_queue:
				print(user_id, "already ate lunch.")
				print()
				break
			elif len(in_queue) == N*M:
				print("There are no more seats.")
				break
			else:
				cal_seat(user_id)
	else:		#Out
		if user_id not in in_queue and user_id not in out_queue:
			print(user_id, "didn't eat lunch.")
		elif user_id in out_queue:
			print(user_id, "already left seat.")
		elif user_id in in_queue:
			# print(in_dict)
			idx_x, idx_y = in_dict[user_id][0]+1, in_dict[user_id][1]+1
			in_queue.remove(user_id)
			out_queue.append(user_id)
			map[idx_x-1][idx_y-1] = 0
			print(user_id, "leaves from the seat ("+str(idx_x)+", "+str(idx_y)+").")
			# print_map()