[Samsung] 2021-2 오전 1번 놀이기구 탑승

[Samsung] 2021-2 오전 1번 놀이기구 탑승

Question

Language: Python

Difficulty: Gold 5

해당 문제는 학생들을 주어진 우선순위에 따라 자리에 배치하는 것을 구현하는 문제로, 정렬을 수행하여 가장 높은 우선순위를 가지는 자리에 학생을 배치한다.

우선순위는 주위에 좋아하는 학생이 많은 칸, 주위에 빈칸이 많은 칸, 행,열이 작은 칸이 높은 우선순위를 가진다. 그렇기 때문에 이 모든것을 정렬의 키로 설정해서 가장 높은 우선순위를 가지는 자리를 찾는다.

Solution

def put_student(favorities_map,board,student_num):
    candidates=[]
    for row in range(n):
        for col in range(n):
            favorite_count=0
            blank_count=0
            #해당 칸이 빈칸이 아닌 경우 넘어간다.
            if board[row][col] != -1:
                continue
            for dir in range(4):
                next_row=row+dy[dir]
                next_col=col+dx[dir]

                #격자를 벗어나는 지 확인
                if not check_range(next_row,next_col):
                    continue
                
                next_student_num=board[next_row][next_col]
                #빈 칸인 경우
                if next_student_num==-1:
                    blank_count+=1
                    continue
                
                #옆 학생이 좋아하는 학생인 경우 
                if favorities_map[student_num][next_student_num]:
                    favorite_count+=1

            candidates.append((-favorite_count,-blank_count,row,col))

    #좋아하는 학생이 많은 순, 빈칸이 많은 순, 행,열이 작은 순으로 정렬
    candidates.sort()
    row,col=candidates[0][2],candidates[0][3]

    board[row][col]=student_num

#각 학생의 점수들을 구해서 총합을 구한다.
def calculate_points(favorities_map,board):
    total_point=0
    for row in range(n):
        for col in range(n):
            student_num=board[row][col]
            favorite_count=0
            for dir in range(4):
                next_row=row+dy[dir]
                next_col=col+dx[dir]

                #격자를 벗어나는 지 확인
                if not check_range(next_row,next_col):
                    continue
                
                next_student_num=board[next_row][next_col]

                #옆 학생이 좋아하는 학생인 경우 
                if favorities_map[student_num][next_student_num]:
                    favorite_count+=1
            
            point=10**(favorite_count-1) if favorite_count >=1 else 0
            total_point+=point
                
    return total_point

#범위 확인
def check_range(row,col):
    if row < 0 or row>=n or col < 0 or col>=n:
        return False
    return True
    
def solution():
    student_orders=[]
    favorities_map=[[False] * (n**2) for _ in range(n**2)]

    #각자 자신이 좋아하는 학생에 대한 매핑 저장
    for index in range(n**2):
        student_num=student_infos[index][0]-1
        favorite_students=student_infos[index][1:]
        student_orders.append(student_num)
        for favorities_student in favorite_students:
            favorities_map[student_num][favorities_student-1]=True
    
    #자리의 정보가 저장된 배열
    board=[[-1]*n for _ in range(n)]

    #각 학생들을 배치한다.
    for student_num in student_orders:
        put_student(favorities_map,board,student_num)
    
    print(calculate_points(favorities_map,board))
    
    
if __name__ == "__main__":
    n=int(input())
    student_infos=[list(map(int,input().split())) for _ in range(n**2)]
    dy=[-1,0,1,0]
    dx=[0,1,0,-1]
    solution()