문제 링크
https://www.acmicpc.net/problem/21608
🕒 Python 풀이시간: 20분
n=int(input())
board=[[0]*n for _ in range(n)]
dx=[-1,1,0,0]
dy=[0,0,-1,1]
liked_dict_for_score=dict()
for i in range(1,n*n+1):
arr=list(map(int,input().split()))
now=arr[0]
list_of_liked=set(arr[1:])
liked_dict_for_score[now]=list_of_liked
seat_list=[]
for i in range(n):
for j in range(n):
if board[i][j]!=0:
continue
near_liked_cnt=0
blank_cnt=0
for k in range(4):
nx=i+dx[k]
ny=j+dy[k]
if nx<0 or ny<0 or nx>=n or ny>=n:
continue
if board[nx][ny] in list_of_liked:
near_liked_cnt+=1
if board[nx][ny]==0:
blank_cnt+=1
seat_list.append((near_liked_cnt,blank_cnt,i,j))
seat_list.sort(key=lambda x:(-x[0],-x[1],x[2],x[3]))
board[seat_list[0][2]][seat_list[0][3]]=now
answer=0
for i in range(n):
for j in range(n):
like_cnt=0
for k in range(4):
nx=i+dx[k]
ny=j+dy[k]
if nx<0 or ny<0 or nx>=n or ny>=n:
continue
if board[nx][ny] in liked_dict_for_score[board[i][j]]:
like_cnt+=1
if like_cnt>0:
answer+=10**(like_cnt-1)
print(answer)
학생 배치의 수학적 미학 📚✨
상어 초등학교에서 n*n의 크기의 교실과 그 수에 맞는 학생들의 번호가 1부터 주어질 때, 각 학생들이 좋아하는 학생의 리스트 또한 4명씩 주어진다. 이 때 세가지 기준에 따라 학생들을 앉혀 이 때의 점수를 좋아하는 사람이 사방에 몇명이 있는지에 따라 구해 출력하면 된다.
1. 비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다.
2. 1을 만족하는 칸이 여러 개이면, 인접한 칸 중에서 비어있는 칸이 가장 많은 칸으로 자리를 정한다.
3. 2를 만족하는 칸도 여러 개인 경우에는 행의 번호가 가장 작은 칸으로, 그러한 칸도 여러 개이면 열의 번호가 가장 작은 칸으로 자리를 정한다.
각 기준이 여러개이기도 하고 한자리씩 탐색하면서 해당의 조건을 전부 탐색해볼 수 있기 때문에 주어진 학생부터 앉히면서 해당 케이스에 필요한 조건을 전부 찾을 수 있다. 모든 자리를 순회하며 4명의 좋아하는 사람이 주위에 있는지, 빈자리가 몇개인지, 행과 열의 번호가 몇인지를 전부 담은 후, 이를 기준에 따라 정렬하면 맨 앞에 리스트에 담겨있는 자리가 해당기준에 가장 적합한 자리이다.
해당 자리에 학생을 앉혀가며 모든 자리에 앉힌 후, 각 좋아하는 사람을 dict과 그 내부에 set으로 두어 탐색하고 몇명인지 구해 점수를 구하면 된다.
이렇게 Python으로 백준의 "상어 초등학교" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊
