백준 21608번 상어 초등학교 문제 풀이(Python, 구현, Gold 5)

백준 21608번 상어초등학교 문제 바로가기

문제 접근

이 문제는 두 부분으로 나누어 풀 수 있겠다.

• 자리 배치하기
• 만족도 구하기

자리 배치하기에서는 모든 자리의 상하좌우를 확인해서 빈칸이 몇개인지, 좋아하는 사람이 몇명있는지를 저장한다.
이렇게 저장한 내용들을 우선순위에 따라서 정렬하고 가장 적합한 자리에 이 학생을 앉힌다.

만족도 구하기는 이미 자리를 다 정해놨기 때문에 이중for문을 통해서 각 자리의 상하좌우를 확인하고 좋아하는 사람의 숫자에 따라 점수를 부여한다.

문제 해결

자리 배치하기

lambda를 이용하여 정렬해주었다. 우선순위가 좋아하는사람의 수, 빈칸의 수, 행, 열이기에 이에 맞게 sort해준다.
sort한 결과에서 pop을 통해 가장 조건에 맞는 자리를 구한다.
이렇게 구한 자리에 학생을 앉히고 다시 실행한다.

 for i in range(N):
 	for j in range(N):
 	if pan[i][j] == 0: # 빈칸이면
 		blank = 0 #주위 빈칸 개수
 		like = 0 #주위 좋아하는 사람의 개수
 		
 		for index in range(4): #주변 확인
        	ni = i + dx[index]
 			nj = j + dy[index]
          if ni<0 or nj<0 or ni>=N or nj>=N: #예외 제거
              continue
          if pan[ni][nj] == 0:
              blank += 1
          elif pan[ni][nj] in s[s_num]:
              like += 1
    	can_list.append([i, j, blank, like])
    
    can_list.sort(key=lambda x: (x[3], x[2], -x[0],-x[1]))
    i,j,blank,like = can_list.pop()
    pan[i][j] = s_num

만족도 구하기

만족도 역시 마찬가지로 각 자리의 상하좌우를 확인하여 좋아하는 사람의 숫자를 구해야한다.
이렇게 구한 숫자로 각 자리의 만족도를 구하여 result에 더해주면 된다.

result = 0
for i in range(N):
    for j in range(N):
        like = 0 #주위 좋아하는 사람의 개수
        
        for index in range(4): #주변 확인
            ni = i + dx[index]
            nj = j + dy[index]
            if ni<0 or nj<0 or ni>=N or nj>=N: #예외 제거
                continue
            if pan[ni][nj] in s[pan[i][j]]:
                like += 1
        
        if like == 0:
            good = 0
        if like == 1:
            good = 1
        if like == 2:
            good = 10
        if like == 3:
            good = 100
        if like == 4:
            good = 1000

        result += good

제출 코드

import sys
N = int(sys.stdin.readline())
s = dict()
pan = [[0 for i in range(N)] for j in range(N)]
dx = [0,0,1,-1]
dy = [1,-1,0,0]
for _ in range(N**2):
    line = list(map(int, sys.stdin.readline().split()))
    s_num = line[0]
    s[s_num] = [line[1],line[2],line[3],line[4]]

    can_list = [] # 자리 후보들

    for i in range(N):
        for j in range(N):
            if pan[i][j] == 0: # 빈칸이면
                blank = 0 #주위 빈칸 개수
                like = 0 #주위 좋아하는 사람의 개수
                
                for index in range(4): #주변 확인
                    ni = i + dx[index]
                    nj = j + dy[index]
                    if ni<0 or nj<0 or ni>=N or nj>=N: #예외 제거
                        continue
                    if pan[ni][nj] == 0:
                        blank += 1
                    elif pan[ni][nj] in s[s_num]:
                        like += 1
                can_list.append([i, j, blank, like])
    
    can_list.sort(key=lambda x: (x[3], x[2], -x[0],-x[1]))
    i,j,blank,like = can_list.pop()
    pan[i][j] = s_num
   
result = 0
for i in range(N):
    for j in range(N):
        like = 0 #주위 좋아하는 사람의 개수
        
        for index in range(4): #주변 확인
            ni = i + dx[index]
            nj = j + dy[index]
            if ni<0 or nj<0 or ni>=N or nj>=N: #예외 제거
                continue
            if pan[ni][nj] in s[pan[i][j]]:
                like += 1
        
        if like == 0:
            good = 0
        if like == 1:
            good = 1
        if like == 2:
            good = 10
        if like == 3:
            good = 100
        if like == 4:
            good = 1000

        result += good

print(result)