21608. 상어 초등학교

lambda와 sort를 이용해서 좋아하는 학생이 인접한 칸에 가장 많은 칸, 인접한 칸 중에서 비어있는 칸이 가장 많은 칸, 행 번호가 가장 작은 칸, 열 번호가 가장 작은 칸으로 한꺼번에 정렬하였다.

import collections, sys
input = sys.stdin.readline
n = int(input())
likeList = collections.defaultdict(list)
#key: 학생 번호 / value: 좋아하는 학생의 번호 리스트
matrix = [[0]*n for _ in range(n)]
x = [1, -1, 0, 0]
y = [0, 0, 1, -1]

#학생 번호와 좋아하는 학생의 번호 리스트가 한 줄로 들어오기 때문에 해당 과정을 거침
for i in range(n**2):
    line = list(map(int, input().split()))
    for j in range(4):
        likeList[line[0]].append(line[1+j])
        
def cntPos(like, px, py):
    friendCnt, emptyCnt = 0, 0 
    #friendCnt: 인접한 칸에 있는 좋아하는 학생의 수
    #emptyCnt: 인접한 칸이 빈 칸인 수
    
    if matrix[px][py] != 0:
        return -1, -1
    #이미 자리에 학생이 앉아있는 경우 바로 리턴
    #-1, -1인 이유는 인접한 칸에 좋아하는 학생 수도 없고 빈 칸도 없는 경우와 다른 경우이기 때문
    
    for i in range(4):
        nx = x[i] + px
        ny = y[i] + py
        if nx >= 0 and nx < n and ny >= 0 and ny < n:
            if like:
                if matrix[nx][ny] in like:
                    friendCnt += 1
                    #인접한 칸에 좋아하는 학생이 있다면 1 증가
            if matrix[nx][ny] == 0:
                emptyCnt += 1
                #인접한 칸에 빈 칸이 있다면 1 증가
            
    return friendCnt, emptyCnt
        
for student in likeList:
    like = likeList[student] #좋아하는 학생 번호 리스트
    arr = []
    for i in range(n):
        for j in range(n):
            friendCnt, emptyCnt = cntPos(like, i, j)
            arr.append([friendCnt, emptyCnt, i, j])
    arr.sort(key=lambda x: (-x[0],-x[1], x[2]))
    #좋아하는 학생이 인접한 칸에 가장 많은 칸
    #인접한 칸 중에서 비어있는 칸이 가장 많은 칸
    #행 번호가 가장 작은 칸
    #열 번호가 가장 작은 칸으로 정렬
    matrix[arr[0][2]][arr[0][3]] = student

result = 0
for i in range(n):
    for j in range(n):
        likeCnt = 0 #좋아하는 학생의 수
        for k in range(4):
            nx = x[k] + i
            ny = y[k] + j
            if nx >= 0 and nx < n and ny >= 0 and ny < n:
                if matrix[nx][ny] in likeList[matrix[i][j]]:
                    likeCnt += 1
        if likeCnt:
            result += 10**(likeCnt-1)
print(result)