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

문제 링크

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

21608번: 상어 초등학교

 

풀이 

완전 탐색 문제 

1. 학생을 자리에 배치할 때마다 graph를 완전 탐색하여 자리 별 인접한 칸의 좋아하는 학생 수와 빈칸 수를 구해서 heap에 삽입

2. heap에 (- 좋아하는 학생 수, - 빈칸 수, 행 번호, 열 번호) 를 삽입시켜줘서 조건에 맞는 자리 pop 

3. graph에 학생 번호 표시하고, sheet 에 학생 자리 위치를 기록

4. sheet을 통해 만족도 구하기 

# https://www.acmicpc.net/problem/21608
import heapq 
n = int(input())

order = []
student =  [ [] for _ in range(n**2 +1 )] 

for _ in range(n**2):
    a, b, c, d, e = map(int,input().split())
    # idx -> 학생 번호, 학생 별 좋아하는 
    student[a] = [b,c,d,e]
    # 자리 배치 순서 
    order.append(a)

graph = [[0] * n for _ in range(n)]

# 학생 별 자리 위치 저장 
sheet = [[] for _ in range(n**2 + 1)]
dx = [1,-1,0,0]
dy = [0,0,1,-1]

for num in order :
    q = []
    
    # 자리 별 인접한 칸의 좋아하는 사람 수와 빈칸 개수 heap에 삽입 
    for x in range(n):
        for y in range(n):
            cnt = 0 
            blank = 0
            # 이미 앉은 자리면 패스 
            if graph[x][y] :
                continue 
            
            for z in range(4):
                nx = x + dx[z]
                ny = y + dy[z]
                
                if nx < 0 or nx >= n or ny < 0 or ny >= n :
                    continue 
                if graph[nx][ny] in student[num]:
                    cnt += 1 
                if graph[nx][ny] == 0 :
                    blank +=1 
            
            heapq.heappush(q, (-cnt, -blank, x, y))
    
    tmp = heapq.heappop(q)
    
    # 학생 자리 표시 
    graph[tmp[2]][tmp[3]] = num
    # 학생 자리 위치 저장 
    sheet[num] = (tmp[2], tmp[3])
    
ans = 0 

# 만족도 구하기 
for i in range(1, n**2 + 1):
    x, y = sheet[i]
    cnt = 0 
    for j in range(4):
        nx = x + dx[j]
        ny = y + dy[j]
        
        if nx < 0 or nx >= n or ny < 0 or ny >= n :
            continue 
        
        if graph[nx][ny] in student[i]:
            cnt += 1
        
    if cnt == 0:
        continue 
    
    ans += 10**(cnt-1) 
        
print(ans)