[백준 21608] 상어 초등학교(구현/브루트포스, python)

 

21608번: 상어 초등학교

처음에 max_count, max_like 를 저장해가면서 x,y변수만 저장해가면서 했는데, 안되더라...

왜안됐을까..

그리고 2차원 배열 만들 때 X처럼 만들면 옅은복사 문제가 생기니 쓰지 말 것.

board = [[0]*N]*N # X

board = [[0 for _ in range(N)] for _ in range(N)] # O

'''
상어 초등학교
https://www.acmicpc.net/problem/21608
1.상하좌우 (인접)
2.좋아하는 학생이 인접한 칸에 (친구랑 앉고 싶음)
3. 2번 칸중 행번호가 가장 작은 칸(숫자 낮은(제일 위쪽)), 그다음은 제일 왼쪽.(좌상)
'''
import sys
import collections
input = sys.stdin.readline

N = int(input())
students = collections.defaultdict(list)
dir_r = [-1, 0, 1, 0]
dir_c = [0, 1, 0, -1]
board = [[0 for _ in range(N)] for _ in range(N)]
for _ in range(N*N):
    a = list(map(int,input().rstrip().split()))
    student = a[0]
    like = a[1:]
    students[student] = like
    
# 모든 학생들 탐색
for student, like in students.items():
    tmp= []
    #각 학생들에 대해서 board를 탐색하면서 자리 정보 tmp에 저장
    for r in range(N):
        for c in range(N):
            count = 0
            like_count=0
            
            if board[r][c] != 0:
                continue
            for d in range(4):
                x, y = r+ dir_r[d], c+dir_c[d]
                if x<0 or x>=N or y<0 or y>=N:
                    continue
                if board[x][y] == 0:
                    count +=1
                if board[x][y] in like:
                    like_count +=1
            tmp.append([like_count, count, r, c])
    # 자리정보 정렬
    tmp.sort(key = lambda x: (-x[0],-x[1], x[2],x[3]))
    # 가장 앞에 있는 자리가 베스트.
    board[tmp[0][2]][tmp[0][3]] = student
            

sum =0
for r in range(N):
    for c in range(N):
        happiness = 0
        for d in range(4):
            x, y = r+dir_r[d] , c+dir_c[d]
            if x < 0 or x >= N or y <0 or y >= N:
                continue
            if board[x][y] in students[board[r][c]]:
                happiness+=1
        if happiness == 2:
            happiness = 10
        elif happiness == 3:
            happiness = 100
        elif happiness == 4:
            happiness = 1000
        sum += happiness
print(sum)