[백준] 21608번: 상어 초등학교 (Python)

 

 

 

 

 

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

21608번: 상어 초등학교

 

 

 

 

 

✅  Solution

• 문제에 나온 대로 구현하면 된다!
• students 배열을 돌면서 각 학생이 앉을 수 있는 자리를 모두 구해 정렬한 뒤, 학생의 자리를 정한다.
  • 먼저 모든 자리를 돌면서 빈자리가 있는지 확인한다.
  • 만약 빈자리가 있다면, 그 자리에서 거리가 1인 방향을 모두 확인하여 주위에 학생이 좋아하는 학생이 있는지 확인한 후, prefer 변수에 더해준다.
  • 그리고 주위에 빈자리가 있다면 empty 변수에 더해준다.
  • 주위 네 방향을 모두 확인한 후, (행, 열, 좋아하는 학생의 수, 빈자리의 수)를 배열에 담아준다.
  • 빈자리 모두 확인하고 나서 정렬한 뒤, 제일 먼저 오는 자리에 학생을 넣어준다.
• 모든 자리에 학생이 있다면 점수를 계산한다.
  • 주위 돌면서 좋아하는 학생의 수를 세서 answer에 더해준다.

 

 

 

 

 

✅  Code

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

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

for student in students:
    available = []

    for i in range(n):
        for j in range(n):
            # 빈자리가 있다면
            if data[i][j] == 0:
                prefer, empty = 0, 0
                
                # 동서남북 방향 확인하여 
                for k in range(4):
                    nx = i + dx[k]
                    ny = j + dy[k]
                     
                    # 범위내에 있을 때
                    if 0 <= nx < n and 0 <= ny < n:
                        # 좋아하는 학생이 주위에 있다면 더해준다.
                        if data[nx][ny] in student[1:]:
                            prefer += 1
                            
                        # 빈자리가 있다면 더해준다.
                        if data[nx][ny] == 0:
                            empty += 1

                available.append((i, j, prefer, empty))
    # 정렬
    available.sort(key= lambda x: (-x[2], -x[3], x[0], x[1]))
    data[available[0][0]][available[0][1]] = student[0]

answer = 0
score = [0, 1, 10, 100, 1000]
students.sort()

for i in range(n):
    for j in range(n):
        count = 0

        for k in range(4):
            nx = i + dx[k]
            ny = j + dy[k]

            if 0 <= nx < n and 0 <= ny < n:
                if data[nx][ny] in students[data[i][j] - 1]:
                    count += 1

        answer += score[count]

print(answer)