[백준] 21608 - 상어 초등학교 (파이썬, Python)

https://pixabay.com/ko/photos/우산-햇빛-여자-비-빛-6239364/

 

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

21608번: 상어 초등학교

 

해당 문제는 구현 문제입니다.

문제의 목표는 규칙에 따라 학생 들의 자리를 배치하고, 학생의 만족도 총합을 계산하는 것입니다.

 

자리를 배치하는 규칙에 따르면 빈 자리 중 우선순위가 높은 자리는 아래의 순서로 결정됩니다.

주위에 좋아하는 학생 수 가 많음 > 주위에 빈 자리가 많음 > 행의 번호가 작음 > 열을 변호가 작음

 

따라서 빈 자리를 찾고, 위 우선순위대로 정렬한 후 가장 우선순위가 높은 자리에 학생을 배치하면 됩니다.

 

학생 만족도 계산은 학생 별로 주위의 좋아하는 학생 수를 찾고, 학생 수 별로 점수를 계산을 하면 됩니다.

 

전체 코드

제출 언어: PyPy3

시간: 300ms

 

import sys

def choose():
    global N, mat, data, order

    for s in order:
        likes = data[s]

        candidates = []
        
        for i in range(N):
            for j in range(N):
                likes_cnt = 0
                blank_cnt = 0

                if mat[i][j] == 0:
                    for k in range(4):
                        nr, nc = i+dy[k], j+dx[k]

                        if 0 <= nr < N and 0 <= nc < N:
                            if mat[nr][nc] == 0:
                                blank_cnt += 1

                            elif mat[nr][nc] in likes:
                                likes_cnt += 1
                    
                    candidates.append((likes_cnt, blank_cnt, i, j))
        
        _, _, seat_r, seat_c = sorted(candidates, key = lambda x: (-x[0], -x[1], x[2], x[3]))[0]
        mat[seat_r][seat_c] = s

def cal():
    global N, mat, data, dy, dx
    score = 0

    for i in range(N):
        for j in range(N):
            s = mat[i][j]
            likes = data[s]
            likes_cnt = 0

            for k in range(4):
                nr, nc = i+dy[k], j+dx[k]

                if 0 <= nr < N and 0 <= nc < N:
                    if mat[nr][nc] in likes:
                        likes_cnt += 1
            
            if likes_cnt == 1:
                score += 1
            elif likes_cnt == 2:
                score += 10
            elif likes_cnt == 3:
                score += 100
            elif likes_cnt == 4:
                score += 1000

    return score
                

if __name__ == "__main__":
    N = int(sys.stdin.readline().strip())

    mat = [ [0] * N for _ in range(N) ]
    data = {}
    order = []

    answer = 0
    dy, dx = (-1, 0, 1, 0), (0, 1, 0, -1)

    for _ in range(N*N):
        s1, s2, s3, s4, s5 = map(int, sys.stdin.readline().strip().split())

        data[s1] = [s2, s3, s4, s5]
        order.append(s1)

    choose()

    answer = cal()

    print(answer)

---

읽어 주셔서 감사합니다 :)

틀린 부분이 있다면 댓글로 편히 알려주세요😊