백준 boj 21608. 상어초등학교

코드

f = open('input.txt', 'r')
N = int(f.readline().strip())
friends_info = {}

for _ in range(N*N):
  fi = list(map(int, f.readline().strip().split()))
  friends_info[fi[0]] = fi[1:]
# print(friends_info)

grid = [[0]*N for _ in range(N)]
score = {0:0, 1:1, 2:10, 3:100, 4:1000}
ans = 0

def calcluate(r,c,s):
  n_fr, n_vac_s = 0, 0

  for dx, dy in ((-1,0),(1,0),(0,1),(0,-1)):
    ni, nj = r+dx, c+dy
    if 0<=ni<N and 0<=nj<N:
      if grid[ni][nj] in friends_info[s]:
        n_fr += 1
      elif grid[ni][nj] == 0: 
        n_vac_s += 1
  return n_fr, n_vac_s

for s, fr in friends_info.items():
  mx_fr, mx_fr_nvac = -1e8, -1e8

  ## 학생마다 자리 찾아주기. 
  for r in range(N):
    for c in range(N):
      if grid[r][c] == 0:
        n_fr, n_vac_s = calcluate(r,c,s) ## (r,c)의 인접 친구와 인접한 빈자리의 갯수 구하기.

        if n_fr > mx_fr:
          mx_fr = n_fr
          mx_fr_nvac = n_vac_s
          si, sj = r, c
        elif n_fr == mx_fr:
          if n_vac_s > mx_fr_nvac: # mx_fre_nvac 갱신. 
            mx_fr_nvac = n_vac_s
            si, sj = r, c

  grid[si][sj] = s

for r in range(N):
  for c in range(N):
    s = grid[r][c]
    n_fr = 0
    for dx, dy in ((0,1),(1,0),(0,-1),(-1,0)):
      ni, nj = r+dx, c+dy
      if 0<=ni<N and 0<=nj<N and (grid[ni][nj] in friends_info[s]):
        n_fr += 1
    ans += score[n_fr]

print(ans)