[백준 21608번] 상어 초등학교

n = int(input())

data = [[] for _ in range(n**2)]
location = [[0]*n for _ in range(n)]

dx = [-1,1,0,0]
dy = [0,0,-1,1]

like_dict = {}
sequence = []

total = 0

for i in range(n**2):
    data[i] = list(map(int, input().split()))

for i in range(n**2):
    sequence.append(data[i][0])
    for j in range(1,5):
        if like_dict.get(data[i][0]) == None:
            like_dict[data[i][0]] = {data[i][j]}
        else:
            like_dict[data[i][0]].add(data[i][j])

def getLike(num): # 인접한 좋아하는 학생이 가장 많은 자리 목록 (1번 조건)
    result_list = [] 
    max_value = -1
    for i in range(n):
        for j in range(n):
            if location[i][j] != 0: # 이미 자리가 있는 경우는 pass
                continue
            temp = 0 # 인접한 좋아하는 사람의 수
            for k in range(4):
                nx = i + dx[k]
                ny = j + dy[k]
                if nx >= 0 and nx < n and ny >= 0 and ny < n:
                    if (location[nx][ny] in like_dict[num]):
                        temp += 1
            if (temp > max_value):
                result_list = [(i,j)]
                max_value = temp
            elif (temp == max_value):
                result_list.append((i,j))
    return result_list

def getEmpty(locations): # 인접한 빈칸이 가장 많은 자리 목록 (2번 조건)
    result_list = []
    max_value = -1
    
    for coor in locations:
        temp = 0
        x, y = coor[0], coor[1]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx >= 0 and nx < n and ny >= 0 and ny < n:
                if location[nx][ny] == 0:
                    temp += 1
        if temp > max_value:
            result_list = [(x,y)]
            max_value = temp
        elif temp == max_value:
            result_list.append((x,y))

    return result_list


def compareRowAndColumn(locations): # 행과 열의 인덱스가 가장 작은 자리 (3번 조건)

    result_list = []
    result = (0,0)
    min_x,min_y = 21, 21
    
    for coor in locations: # 행 구별
        x,y = coor[0], coor[1]
        if x < min_x:
            result_list = [(x,y)]
            min_x = x
        elif x == min_x:
            result_list.append((x,y))
    
    for coor in result_list: # 열 구별
        x,y = coor[0], coor[1]
        if y < min_y:
            result = (x,y)
            min_y = y

    return result

for index in sequence:
    like_list = getLike(index)
    empty_list = getEmpty(like_list)
    final_location = compareRowAndColumn(empty_list)
    x,y = final_location[0], final_location[1]
    location[x][y] = index

for i in range(n):
    for j in range(n):
        index = location[i][j]
        temp = 0
        for k in range(4):
            nx = i + dx[k]
            ny = j + dy[k]
            if nx >= 0 and nx < n and ny >= 0 and ny < n:
                if location[nx][ny] in like_dict[index]:
                    temp += 1
        if temp == 0:
            total += 0
        elif temp == 1:
            total += 1
        elif temp == 2:
            total += 10
        elif temp == 3:
            total += 100
        elif temp == 4:
            total += 1000

print(total)

이번 문제는 주어진 조건에 맞게 학생들을 자리에 배치하고, 각 자리에 앉은 학생들의 만족도를 구하는 문제이다. 특별한 알고리즘이 필요한 것은 아니지만, 여러가지 조건과 로직을 구현해야 한다는 점에서 조금 까다로웠던 문제였다 🥲

 

이 문제에서 필요한 로직은 다음 3가지로 정리해볼 수 있다.

1. 좋아하는 학생의 수가 가장 많은 자리 목록을 구하는 로직 (getLike)
2. 비어있는 칸이 가장 많은 자리 목록을 구하는 로직 (getEmpty)
3. 행과 열이 가장 작은 자리를 구하는 로직 (compareRowAndColumn)

위 로직들을 하나의 함수로 만들어서 구현한 결과 한번에 풀이할 수 있었다. 조건은 상당히 복잡한 문제였지만 로직을 분리하여 풀이하니 조금 더 수월하게 풀 수 있었던 것 같다 :)