백준/python 21608 상어 초등학교

# @Date : 2024-09-03 15:05:58
# @Author : ecodev
# @Link : http://ecodev-blog.vercel.app

import sys
input = sys.stdin.readline

############ ---- Input Functions ---- ############


def inp():
    return(int(input()))


def inlt():
    return(list(map(int, input().split())))


def insr():
    s = input()
    return(list(s[:len(s) - 1]))


def invr():
    return(map(int, input().split()))


n = inp()
dic = {}
graph = [[0] * n for _ in range(n)]
start = 0
path = [(1, 0), (-1, 0), (0, 1), (0, -1)]

for i in range(n ** 2):
    ls = inlt()
    dic[ls[0]] = ls[1:]


for i in dic:
    max_like = -1
    max_empty = -1
    temp_x = -1
    temp_y = -1
    for j in range(n):
        for k in range(n):
            # 빈칸이면 -> 빈칸 주위 탐색
            if graph[j][k] == 0:
                like, empty = 0, 0
                for l in range(4):
                    nx = j + path[l][0]
                    ny = k + path[l][1]
                    if 0 <= nx < n and 0 <= ny < n:
                        if graph[nx][ny] in dic[i]:
                            like += 1
                        elif graph[nx][ny] == 0:
                            empty += 1
                if max_like < like: # 1번 조건 로직
                    temp_x = j
                    temp_y = k
                    max_like = like
                    max_empty = empty

                elif max_like == like: # 2번 조건 로직
                    if max_empty < empty:
		                    # 여기서 부등호를 <= 사용하지 않음으로써 3번 조건까지 만족
		                    # 이유 : 우리는 이중 for문을 사용하면서 위에서 아래로 내려오고 있기 때문.
                        max_empty = empty
                        temp_x = j
                        temp_y = k
                     

    graph[temp_x][temp_y] = i

result = 0
score = [0, 1, 10, 100, 1000]
for i in range(n):
    for j in range(n):
        cnt = 0
        for k in range(4):
            nx = i + path[k][0]
            ny = j + path[k][1]
            if 0 <= nx < n and 0 <= ny < n:
                if graph[nx][ny] in dic[graph[i][j]]:
                    cnt += 1

        result += score[cnt]

print(result)