[BOJ] 상어 초등학교 - 21608 (G5)

시간 제한	메모리 제한
2 초	512 MB

문제

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

학생은 1번부터 N²번까지 번호가 매겨져 있고, (r, c)는 r행 c열을 의미한다. (r, c)의 인접한 칸은 (r-1, c), (r+1, c), (r, c-1), (r, c+1)이다.

학생이 좋아하는 학생 4명이 주어지고, 다음 순서로 자리를 배정한다.

1. 비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다.
2. 1을 만족하는 칸이 여러 개이면, 인접한 칸 중에서 비어있는 칸이 가장 많은 칸으로 자리를 정한다.
3. 2를 만족하는 칸도 여러 개인 경우에는 행의 번호가 가장 작은 칸으로, 그러한 칸도 여러 개이면 열의 번호가 가장 작은 칸으로 자리를 정한다.

학생의 만족도는 자리 배치가 모두 끝난 후에 구할 수 있다. 학생의 만족도를 구하려면 그 학생과 인접한 칸에 앉은 좋아하는 학생의 수를 구해야 한다. 그 값이 0이면 0, 1이면 1, 2이면 10, 3이면 100, 4이면 1000이다.

풀이

구현 문제이다. 주어진 규칙대로 정확하게 구현하면 된다.

코드

N = int(input())

class_room = [[0] * N for _ in range(N)]
like_list = [[] for _ in range(N ** 2 + 1)]
students = [list(map(int, input().split())) for _ in range(N ** 2)]
for s in students:
    like_list[s[0]] = s[1:]

dij = ((-1, 0), (1, 0), (0, -1), (0, 1))

def find_seat(n):
    like = like_list[n]
    max_pref = []
    
    for i in range(N):
        for j in range(N):
            if class_room[i][j] != 0:
                continue

            like_cnt = 0
            empty_cnt = 0

            for di, dj in dij:
                ni, nj = i + di, j + dj
                if 0 <= ni < N and 0 <= nj < N:
                    if class_room[ni][nj] in like:
                        like_cnt += 1
                    elif class_room[ni][nj] == 0:
                        empty_cnt += 1

            max_pref.append(( -like_cnt, -empty_cnt, i, j))

    max_pref.sort()
    x, y = max_pref[0][2], max_pref[0][3]
    class_room[x][y] = n

def calc_score():
    score = 0
    point = [0, 1, 10, 100, 1000]

    for i in range(N):
        for j in range(N):
            cnt = 0
            n = class_room[i][j]
            like = like_list[n]
            for di, dj in dij:
                ni, nj = i + di, j + dj
                if 0 <= ni < N and 0 <= nj < N:
                    if class_room[ni][nj] in like:
                        cnt += 1
            score += point[cnt]
    return score

for student in students:
    find_seat(student[0])

print(calc_score())

시간 복잡도

O(N^4)