[백준 21608] 상어 초등학교(python)

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

21608번: 상어 초등학교

상어 초등학교 문제

조건에 맞게 학생을 배치 할 경우의 학생의 만족도의 합을 구하는 문제

 

#사용 알고리즘

정렬

 

 

📌문제 접근 포인트

1. 요구 조건이 생각보다 많으므로 요구 조건을 잘 파악하자.

2. |r1-r2|+|c1-c2|=1을 만족하는 두 칸의 의미는 즉, 해당 칸 기준 +에 위치한 칸을 의미한다. +를 탐색할 수 있게 구성해보자.

3. 비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정하고 → 인접한 칸 중에서 비어있는 칸이 가장 많은 칸으로 자리를 정하고 → 행의 번호가 가장 작은 칸으로, 그러한 칸도 여러 개이면 열의 번호가 가장 작은 칸으로 자리를 정한다.의 순서로 자리를 정하게 된다. 즉, 우리가 필요한 항목은 좋아하는 학생 수(likes), 비어있는 칸(empty), 행의 번호(y), 열의 번호(x)이다.
요구 조건에 맞게 람다 함수를 활용하여 각각의 우선 순위에 맞춰 정렬하고, 그때의 위치를 뽑아서 학생들을 배정해보자.

4. 배정이 완료 됐으면, 학생들의 만족도를 구해서 출력하면 성공

⚙ 내가 푼 정답 코드

# 조건 0 : |r1-r2|+|c1-c2|=1을 만족하는 두 칸 = 인접한 칸 (즉 +칸)
# 조건 1 : 빈 칸중 좋아하는 학생이 인접한 칸에 제일 많은 칸으로 자리를 정함
# 조건 2 : 조건1이 여러개면 인접 칸 중에 빈 칸이 가장 많은 칸으로 자리를 정함
# 조건 3 : 조건2도 여러개면 행번호가 가장 작 칸, 그래도 여러개면 열이 작은 칸
# 조건 4 : 만족도를 구해보자 -> if 좋아하는학생수 == 0 0 else 10**배치 완료 후 인접 칸에 좋아하는 학생의 수-1

def check(): # 좋아하는 학생 수와 빈칸이 몇명 인지 체크, 각각의 최대값 구하기
    result = []
    for y in range(N):
        for x in range(N):
            if classroom[y][x] == 0:
                likes, empty = 0, 0
                for dy, dx in move:
                    ny, nx = y + dy, x + dx
                    if 0 <= ny < N and 0 <= nx < N :
                        if classroom[ny][nx] in like: # 좋아하는 학생 수
                            likes += 1
                        if classroom[ny][nx] == 0: # 빈자리 수
                            empty += 1
                result.append([y,x,likes, empty])
    return sorted(result, key=lambda x:(-x[2],-x[3],x[0],x[1])) # like, empty 내림차순, 위치 열, 행순 오름차순 정렬

import sys
N = int(sys.stdin.readline())
classroom = [[0]*N for _ in range(N)]
move = [[0,1],[1,0],[-1,0],[0,-1]]
student_like = {} # 좋아하는 학생 매치시켜주기
for _ in range(N*N):
    num, *like = map(int, sys.stdin.readline().split())
    student_like[num] = like
    x = check()
    classroom[x[0][0]][x[0][1]] = num

result = 0
for y in range(N):
    for x in range(N):
        temp = 0
        for dy, dx in move:
            ny, nx = y + dy, x + dx
            if 0 <= ny < N and 0<= nx < N:
                if classroom[ny][nx] in student_like[classroom[y][x]]: # 좋아하는 학생 번호가 있으면
                    temp += 1 # 학생 수 체크
        if temp > 0 : # 좋아하는 학생이 있다면
            result += 10**(temp-1) # 학생 수에 해당하는 값만큼 증가
print(result)