[백준 21608] 상어 초등학교 - 파이썬

문제

https://www.acmicpc.net/problem/21608

21608번: 상어 초등학교

 

 

 

풀이 방법

n = 3 일 때, 전체 9칸을 차례대로 돌면서 주변에 있는 내가 원하는 번호의 개수와, 빈 자리를 체크하여 리스트에 저장한다.

문제에서 주어진 조건에 맞게 자리 배치를 하기 위해 lambda 함수를 사용해 리스트를 정렬하는데, 원하는 번호의 개수와 빈자리를 내림차순으로, 행과 열을 오름차순으로 정렬한다. 

이렇게 정렬을 마쳤으면 가장 첫 번째 오는 원소에 있는 행과 열에 해당하는 자리에 학생을 앉힌다. 

 

자리에 다 앉혔다면 이제 학생 번호 순서대로 각자가 원하는 번호와 몇개나 인접해있는지 개수를 센다. 

 

 

 

 

코드

n = int(input())
students = [list(map(int, input().split())) for _ in range(n**2)]
arr = [[0]*n for _ in range(n)]

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

for order in range(n**2):
    student = students[order]
    
    tmp = []
    for i in range(n):
        for j in range(n):
            if arr[i][j] == 0:
                like = 0
                blank = 0
                
                for k in range(4):
                    nx = i + dx[k]
                    ny = j + dy[k]
                    
                    if 0 <= nx < n and 0 <= ny < n:
                        if arr[nx][ny] in student[1:]:
                            like += 1
                        if arr[nx][ny] == 0:
                            blank += 1
                            
                tmp.append([like, blank, i, j])
                
    tmp.sort(key = lambda x:(-x[0], -x[1], x[2], x[3]))
    arr[tmp[0][2]][tmp[0][3]] = student[0]
    
        

result = 0
students.sort()


for i in range(n):
    for j in range(n):
        ans = 0
        
        for k in range(4):
            nx = i + dx[k]
            ny = j + dy[k]
            
            if 0 <= nx < n and 0 <= ny < n:
                if arr[nx][ny] in students[arr[i][j]-1]:
                    ans += 1
                    
        if ans != 0:
            result += 10 ** (ans - 1)
            
            
print(result)