[python] 백준 21608 - 상어 초등학교

출처 : 백준, https://www.acmicpc.net/problem/21608

21608번: 상어 초등학교

 

와 이 코드 156ms로 백준에서 Python3 풀이 중에 22등 했다. 대박

 

조건 설명이 너무 어려워서 간단하게만 설명하면,

 

---

 

학생들은 자신이 좋아하는 친구 4명을 선정하여 제출하였습니다.

우리는 다음과 같은 규칙에 따라 학생들의 자리를 선정해야합니다.

 

 

1. 각 자리를 기준으로 상하좌우에 내가 좋아하는 친구가 많이 앉아있는 자리를 우선합니다.

2. 좋아하는 친구가 많이 앉아있는 자리가 여러 개라면, 상하좌우에 빈 자리가 많은 자리를 우선합니다.

3. 위 역시도 여러개라면, 행 번호가 가장 적은 자리를, 행 번호가 같은 자리가 여러 개라면 열 번호가 적은 자리를 우선합니다.

 

---

 

 

풀이

 

class Seat:
  def __init__(self, point):
    self.point = point
    self.around = set()
    self.empty = 4
    self.student = None

class Student:
  def __init__(self, n, friends):
    self.number = n
    self.friends = set(friends)
    self.seat = None

def r0PreSetSeat(number, students, _class, empty_list, n):
  #탐색 범위를 줄이는 함수
  #친구가 앉아있다면 친구 주위의 상하좌우 자리 set을 return하는 함수
  #친구가 한 명도 앉아있지 않다면 빈자리 set을 return하는 함수
  
  r0_set = set()
  dx = [-1, 0, 0, 1]
  dy = [0, -1, 1, 0]

  for friend in students[number].friends:#number에 친구들에 대해서
    if students[friend].seat:#친구가 앉아있다면,
      for index in range(4):#친구 자리의 상좌우하 자리를 r0_set에 넣음.
        x, y = students[friend].seat
        nx, ny = x + dx[index], y + dy[index]

        if 0 < nx <= n and 0 < ny <= n and (nx, ny) in empty_list:
          r0_set.add((nx, ny))
      
  if len(r0_set) > 0:#r0_set에 값이 있다면 r0_set return
    return r0_set
  else:#r0_set에 값이 없다면 empty_list return
    return empty_list
    
def r1r2MostFriendsEmpty(search_seat, friends, _class):
  #좋아하는 학생이 상하좌우에 가장 많은 자리이면서 상하좌우에 빈자리가 많은 자리들을 return하는 함수
  #자리 set을 받고, 상하좌우에 좋아하는 학생의 수, 빈 자리 수를 기준으로 정렬
  #가장 많은 자리들을 return

  r1_dict = dict()

  for seat in search_seat:
    near_friends = len(_class[seat].around & friends)
    near_empty = _class[seat].empty
    if (near_friends, near_empty) in r1_dict:
      r1_dict[(near_friends, near_empty)].append(seat)
    else:
      r1_dict[(near_friends, near_empty)] = [seat]

  r1_sort = sorted(r1_dict.items(), key=lambda x:x[0], reverse=True)
  return set(r1_sort[0][1])

def r3RowCol(search_row_col):
  #자리를 받아서 행->열 순으로 정렬
  #첫번째 성분 return
  return sorted(search_row_col)[0]

def updateSeat(number, seat, students, _class, empty_list, n):
  #students, _class, empty_list 업데이트 하는 함수
  students[number].seat = seat
  _class[seat].student = number
  
  empty_list.remove(seat)

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

  for index in range(4):
    x, y = seat
    nx, ny = x + dx[index], y + dy[index]

    if 0 < nx <= n and 0 < ny <= n and (nx, ny) in empty_list:
      _class[(nx, ny)].empty -= 1
      _class[(nx, ny)].around.add(number)

def calcSatisfaction(students, _class, n):
  #만족도 계산 함수
  dx = [-1, 0, 0, 1]
  dy = [0, -1, 1, 0]
  satisfaction = 0

  for key, value in students.items():
    friends = value.friends
    seat = value.seat
    near_set = set()
    
    for index in range(4):
      x, y = seat
      nx, ny = x + dx[index], y + dy[index]
  
      if 0 < nx <= n and 0 < ny <= n:
        near_set.add(_class[(nx, ny)].student)

    near_friends = len(friends & near_set)

    if near_friends == 1:
      satisfaction += 1
    elif near_friends == 2:
      satisfaction += 10
    elif near_friends == 3:
      satisfaction += 100
    elif near_friends == 4:
      satisfaction += 1000

  return satisfaction

def solution():
  #Setting
  n = int(input())
  _class = dict([[(i+1, j+1), Seat((i+1, j+1))] for j in range(n) for i in range(n)])
  empty_list = set((i+1, j+1) for j in range(n) for i in range(n))
  students = dict()
  
  for i in range(n*n):
    stu, *friends = map(int, input().split())
    students[stu] = Student(stu, friends)

  for i in range(1, n+1):
    _class[(1, i)].empty -= 1
    _class[(n, i)].empty -= 1
    _class[(i, 1)].empty -= 1
    _class[(i, n)].empty -= 1

  for number in students.keys():
    r0_set = r0PreSetSeat(number, students, _class, empty_list, n)
    r1_set = r1r2MostFriendsEmpty(r0_set, students[number].friends, _class)
    seat = r3RowCol(r1_set)
    updateSeat(number, seat, students, _class, empty_list, n)
  
  print(calcSatisfaction(students, _class, n))

solution()

 

---

 

시간 복잡도

 

-

 

알게 된 점

 

-

 

고찰

 

구현 어렵게 내니까 너무 힘들다........

 

Github

백준 21608 - 상어 초등학교