[BOJ] 21608. 상어 초등학교 (python)

✏️ 문제

상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호가 매겨져 있고, (r, c)는 r행 c열을 의미한다. 교실의 가장 왼쪽 윗 칸은 (1, 1)이고, 가장 오른쪽 아랫 칸은 (N, N)이다.
선생님은 학생의 순서를 정했고, 각 학생이 좋아하는 학생 4명도 모두 조사했다. 이제 다음과 같은 규칙을 이용해 정해진 순서대로 학생의 자리를 정하려고 한다. 한 칸에는 학생 한 명의 자리만 있을 수 있고, |r1 - r2| + |c1 - c2| = 1을 만족하는 두 칸이 (r1, c1)과 (r2, c2)를 인접하다고 한다.
비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다.1을 만족하는 칸이 여러 개이면, 인접한 칸 중에서 비어있는 칸이 가장 많은 칸으로 자리를 정한다.2를 만족하는 칸도 여러 개인 경우에는 행의 번호가 가장 작은 칸으로, 그러한 칸도 여러 개이면 열의 번호가 가장 작은 칸으로 자리를 정한다.

 

🤖 알고리즘

 

#구현  

 

 

🤯 풀이 방법

맨 처음에 전체 자리 별 인접 자리를 저장하고 있는 배열을 만든다.
이후 학생 순서대로 이미 차 있지 않은 자리들을 돌며 조건의 순서대로 일치하는 값이 있는지 확인한다.

close는 해당 칸에 대한 인접 칸의 정보가 모두 들어 있다.
student 정보와 like 정보가 들어오면, board i j를 전체 돌면서, 만약 seated[i][j]가 0(false)이라면,

seatedinfo: [["좋아하는 학생의 수", "비어있는 인접칸의 수"]]
1. close[i][j] 안의 값들 중에서 like의 수를 찾아서 체크하여 seatinfo[i][j]에 append
2. close[i][j] 안의 값들 중에서 seated가 false이면 seatinfo에 append

seatinfo를 i j로 돌면서 like가 max인 것을 찾고 하나이면 리턴
두개 이상이면 maxlike 중 empty가 max인것을 찾고 하나이면 리턴
그렇지 않으면 i j를 돌면서 가장 처음 만나는 값을 리턴

자리가 완성된 후 만족도 계산

 

👾 구현 코드 (파이썬)

# [BOJ] 21608. 상어 초등학교
import sys
input = sys.stdin.readline

# 각 자리별 인접 자리를 구하기 위한 함수
def findclose(i, j):
    global close, maxl, maxseat
    seats = []
    for r in range(N):
        for c in range(N):
            if abs(i - r) + abs(j - c) == 1:
                  seats.append([r, c])
                    
    # 인접 조건에 맞는 값들을 close의 해당 위치에 모아두기
    close[i][j] = seats
    # 첫 학생의 자리를 구하기 위해 인접 자리가 가장 많은 값도 구해둠
    if len(seats) > maxl:
        maxl = len(seats)
        maxseat = [i, j]
    return
      
# 각 학생 별 맞는 자리를 찾기 위한 함수
def findseat(stu, like):
    global close
    # 각 자리 별 좋아하는 친구의 수, 비어있는 인접 자리의 수를 구하기 위한 배열
    seatinfo = [[[0, 0]] * N for _ in range(N)]
    maxl, maxe = 0, 0
    for i in range(N):
        for j in range(N):
            # 현재 비어 있는 자리만 대상으로 확인
            if seated[i][j] == 0:
                l, e = 0, 0
                for c in close[i][j]:
                    # 인접한 자리 중에 좋아하는 친구가 있음
                    if board[c[0]][c[1]] in like:
                        l += 1
                    # 인접한 자리가 비어 있음
                    if board[c[0]][c[1]] == 0:
                        e += 1
                # 이후 사용 위해 좋아하는 친구가 가장 많은 자리의 친구 수와, 비어있는 자리의 max값 저장
                maxl = max(maxl, l)
                maxe = max(maxe, e)
                seatinfo[i][j] = [l, e]

    # 조건 1. 친구가 가장 많은 값을 찾자
    maxlike = []
    for i in range(N):
        for j in range(N):
            if seatinfo[i][j][0] == maxl:
                maxlike.append([i, j])
    if len(maxlike) == 1:    # 친구가 가장 많은 자리가 하나이면 바로 return
        return maxlike[0]

    maxee = 0
    maxempty = []
    # 좋아하는 친구의 수가 같은 자리끼리 비어있는 수 비교
    for m in maxlike:
        if seatinfo[m[0]][m[1]][1] > maxee:
            maxee = seatinfo[m[0]][m[1]][1]
            maxempty = [[m[0], m[1]]]
        elif seatinfo[m[0]][m[1]][1] == maxee:
            maxempty.append([m[0], m[1]])
    if len(maxempty) == 1:
        return maxempty[0]
    
    # 그래도 결과가 나오지 않는 경우 행, 열이 가장 작은 자리 찾기
    for m in maxempty:
        if seatinfo[m[0]][m[1]] != [0, 0]:
            return m
        
    # 처음부터 인접 자리에 좋아하는 친구가 한 명도 없었던 경우
    for i in range(N):
        for j in range(N):
            if seated[i][j] == 0:
                return [i, j]
    

N = int(input())  # 학생의 수

L = [list(map(int, input().split())) for _ in range(N ** 2)]

board = [[0] * N for _ in range(N)]
close = [[[]] * N for _ in range(N)]
seated = [[0] * N for _ in range(N)]

maxl = 0
maxseat = []

# 각 자리에 해당하는 인접값들을 모두 구해 둠
for i in range(N):
    for j in range(N):
        findclose(i, j)

# 첫번째 학생의 자리 정하기
board[maxseat[0]][maxseat[1]] = L[0][0]
seated[maxseat[0]][maxseat[1]] = 1

# 두 번째 학생부터 자리 정하고 seated true 처리
for i in range(1, N ** 2):
    stu = L[i][0]
    like = L[i][1:5]
    idx = findseat(stu, like)
    board[idx[0]][idx[1]] = stu
    seated[idx[0]][idx[1]] = 1

answer = 0

# 만족도 구하기
for n in range(N ** 2):
    stu = L[n][0]
    like = L[n][1:5]
    seat = []
    cnt = 0
    for i in range(N):
        for j in range(N):
            if board[i][j] == stu:
                seat = [i, j]
    c = close[seat[0]][seat[1]]
    for cc in c:
        if board[cc[0]][cc[1]] in like:
            cnt += 1
    if cnt != 0:
        answer += 10 ** (cnt - 1)

print(answer)

 

 

 

21608번: 상어 초등학교