[BOJ/Python] 21608.상어 초등학교

📌 문제

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

21608번: 상어 초등학교

 

📌 문제 접근 방법

1. students라는 딕셔너리를 만들어서 학생의 번호를 key, 좋아하는 학생 번호 리스트를 value로 저장했다.
2. room과 like_cnt라는 리스트를 만들어서 각각 학생들의 자리배치와 인접한 칸에 있는 좋아하는 학생 수를 저장했다.
3. students 딕셔너리를 순회하며 room에 비어있는 자리를 모두 체크하였다.
   델타 행렬을 사용하여 비어있는 자리와 인접한 자리를 모두 체크하고 좋아하는 학생 수와 비어있는 칸의 수를 각각 like와 empty에 저장하였다.
4. temp에 (좋아하는 학생 수, 비어있는 칸의 수, 행, 열) 순으로 튜플을 만들어서 저장하고
   첫째로 좋아하는 학생 수를 기준으로 내림차순, 둘째로 비어있는 칸의 수를 기준으로 내림차순,
   다음으로 행과 열을 기준으로 오름차순 정렬을 하였다.
5. temp의 0번째에 있는 행, 열이 문제의 조건에 해당하는 자리이므로 해당 자리(room[temp[0][2]][temp[0][3]])에 학생 번호(num)를 입력한다.
6. 좋아하는 학생의 수(temp[0][0])도 해당 자리(like_cnt[temp[0][2]][temp[0][3]])에 입력하고,
   인접한 자리에 앉은 학생들이 현재 학생을 좋아하는지 확인하여 like_cnt를 갱신해준다.
7. 자리배치가 끝난 후 만족도를 계산하여 출력한다.

 

📌 코드

# 백준 21608 상어 초등학교

N = int(input())

students = {}
for _ in range(N**2):
    input_lst = list(map(int, input().split()))
    students[input_lst[0]] = input_lst[1:]

room = [[0 for _ in range(N)] for _ in range(N)] # 학생들의 자리배치
like_cnt = [[0 for _ in range(N)] for _ in range(N)] # 인접한 칸에 좋아하는 학생 수

dij = [(0, 1), (1, 0), (0, -1), (-1, 0)]

for num, likes in students.items():
    temp = [] # (인접한 칸 중 좋아하는 학생 수, 인접한 칸 중 비어있는 칸의 수, 행, 열)

    for i in range(N):
        for j in range(N):
            if room[i][j]:
                continue

            like = 0
            empty = 0

            # 인접한 칸 탐색
            for di, dj in dij:
                ni, nj = i+di, j+dj

                if 0 <= ni < N and 0 <= nj < N:
                    if not room[ni][nj]:
                        empty += 1
                    elif room[ni][nj] in likes:
                        like += 1
            
            temp.append((like, empty, i, j))
    
    temp.sort(key=lambda x: (-x[0], -x[1], x[2], x[3]))
    # 자리배치
    room[temp[0][2]][temp[0][3]] = num

    # 좋아하는 학생 수
    like_cnt[temp[0][2]][temp[0][3]] = temp[0][0]
    for di, dj in dij:
        ni, nj = temp[0][2]+di, temp[0][3]+dj
        if 0 <= ni < N and 0 <= nj < N and room[ni][nj]:
            if room[temp[0][2]][temp[0][3]] in students[room[ni][nj]]:
                like_cnt[ni][nj] += 1

# 만족도 계산
answer = 0
for i in range(N):
    for j in range(N):
        if like_cnt[i][j] == 1:
            answer += 1
        elif like_cnt[i][j] == 2:
            answer += 10
        elif like_cnt[i][j] == 3:
            answer += 100
        elif like_cnt[i][j] == 4:
            answer += 1000

print(answer)