이번 문제는 삼성 기출 문제로, 입력되는 순서대로 학생의 자리를 배정하는 문제이다. 3가지 조건에 만족하는 자리를 찾아 자리를 배정해야 하기 때문에 비어 있는 자리를 모두 확인해보아야 한다. 이 방법에 대해 생각하던 중에 리스트로 관리하면 쉽게 해결할 수 있겠다는 생각을 하였다.

a학생의 자리를 정하기 위해 전체 자리를 순회하며 [빈자리의 y좌표, 빈자리의 x좌표, 인접하는 좋아하는 학생의 수, 인접하는 빈자리의 수]형태의 리스트를 리스트 안에 담아 놓고, dy, dx를 통해 주변 4 좌표를 확인하며(거리가 1인 좌표는 상하좌우 밖에 없으므로) 인접하는 좋아하는 학생의 수와 인접하는 빈자리의 수를 증가시킨다. 이 방식으로 a학생이 앉을 수 있는 모든 빈자리에 대한 정보를 담은 리스트를 완성시키고, 이 리스트를 3번째 인자, 4번째 인자에 대한 내림차순으로 정렬시킨다.

3번째 인자와 4번째 인자에 대한 내림차순 정렬만 진행하면 3번째 조건에 부합하지 않을 수도 있지 않을까?라고 생각할 수 있지만, 행과 열이 작은 것부터 리스트에 들어갔고, 파이썬의 sort는 입력된 순서를 유지하며 정렬시키기 때문에 3번째 조건 또한 고려된 정렬이 된다.

그리고 첫번째 학생의 경우에는 자리가 1, 1로 고정되는데, 이유는 다음과 같다.

• 모두 빈자리이므로 인접하는 좋아하는 학생의 수는 모든 자리에서 0이다. 즉 1번째 조건은 고려할 수 없다.
• 모두 빈자리이므로 인접하는 좋아하는 학생의 수는 1, 1~n-2, n-2까지의 자리에서 모두 빈자리가 4자리이다. 즉 2번째 조건도 고려할 수 없다.
• 1번째 조건과 2번째 조건을 통과한 1, 1~n-2, n-2 안의 좌표 중에서 행과 열이 작은 좌표는 1, 1이 된다.

이러한 방식으로 학생의 좌석을 지정하였다. 학생의 만족도는 인접하는 좋아하는 학생의 수가 0일 경우에는 0을 증가시키고, 1 이상일 경우에는 10**(result-1)만큼을 증가시키는 방식으로 해결하였다.

Code

n=int(input())
students=[[] for _ in range(n**2+1)]
seat=[[0 for _ in range(n)] for _ in range(n)]
dy, dx=[0, 1, 0, -1], [1, 0, -1, 0]
def get_feel(y, x):
    student=seat[y][x]
    result=0
    for i in range(4):
        ny, nx=y+dy[i], x+dx[i]
        if 0<=ny<n and 0<=nx<n and seat[ny][nx] in set(students[student]):
            result+=1
    if result==0:
        return result
    return 10**(result-1)
for i in range(n**2):
    a, b, c, d, e=map(int, input().split())
    students[a]=[b, c, d, e]
    if i==0:
        seat[1][1]=a
    else:
        cnts=[]
        for j in range(n):
            for k in range(n):
                if seat[j][k]==0:
                    cnts.append([j, k, 0, 0])
                    for l in range(4):
                        ny, nx=j+dy[l], k+dx[l]
                        if 0<=ny<n and 0<=nx<n:
                            if seat[ny][nx] in set(students[a]):
                                cnts[-1][2]+=1
                            elif seat[ny][nx]==0:
                                cnts[-1][3]+=1
        cnts.sort(key=lambda x:(x[2], x[3]), reverse=True)
        seat[cnts[0][0]][cnts[0][1]]=a
answer=0
for i in range(n):
    for j in range(n):
        answer+=get_feel(i, j)
print(answer)