상어 초등학교

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

21608번: 상어 초등학교

문제요약:

n*n 2차원 배열에 학생과 좋아하는 학생의 숫자를 열거한다. 열거 후 

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

위 규칙순으로 자리를 배치 할 때, 학생들의 만족도(근처에 있는 좋아하는 학생수로 결정)의 합을 구하여라

 

소요시간:

35분

 

난이도:

골드5

 

제출횟수 :

1회

 

코딩:

import sys
input = sys.stdin.readline

n = int(input())

students= [list(map(int,input().split())) for _ in range(n**2)]
arr=  [[0]*n for _ in range(n)]
dy = [-1,0,1,0]
dx = [0,1,0,-1]
fav = dict()

for student in students:
    #자리 후보
    chair = []
    fav[student[0]] = set(student[1:])
    student = student[0]
    
    for y in range(n):
        for x in range(n):
            #이미 차있으면 아웃
            if arr[y][x]:
                continue
            #임시
            f_num = 0
            b_num = 0
            for i in range(4):
                ny = y+dy[i]
                nx = x+dx[i]
                if 0<=ny<n and 0<=nx<n:
                    #주변에 fav가 있으면
                    if arr[ny][nx] in fav[student]:
                        f_num+=1
                    #비어있으면
                    if arr[ny][nx] == 0 :
                        b_num+=1
            chair.append([f_num,b_num,y,x])
    #주어진 조건에 따라 중요도 순서로 순서배치
    chair.sort(key = lambda x:(-x[0],-x[1],x[2],x[3]))
    f,b,y,x = chair[0]
    arr[y][x] = student
result = 0
for y in range(n):
    for x in range(n):
        f = 0
        for i in range(4):
            ny = y+dy[i]
            nx = x+dx[i]
            if 0<=ny<n and 0<=nx<n:
                if arr[ny][nx] in fav[arr[y][x]]:
                    f+=1
        if f!=0:
            result +=10**(f-1)
print(result)

매인 알고리즘은 정렬 이지만, 구현문제에 더 가까운 문제라고 생각합니다. 먼저 나중에 만족도를 구할때 특정학생의 좋아하는 학생리스트를 구하기위해 미리 dict함수로 선언해주었고, 포문을 돌며 비어있지 않은 곳 중에서 주변 좋아하는 학생의 수 ,주변에 비어있는 자리수를 구해준뒤, 우선순위에 따라 정렬해주고 가장 우선순위에 있는것을 채택 했습니다. 그 후, 조건에 따라 호감도를 계산해주었습니다.