본문 바로가기
알고리즘 풀이/백준

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

by char_lie 2023. 7. 14.
반응형

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

 

21608번: 상어 초등학교

상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호

www.acmicpc.net

상어 초등학교 문제

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

 

#사용 알고리즘

정렬

 

 

📌문제 접근 포인트

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)
반응형

댓글