[Python](시뮬) 백준 21608번 : 상어 초등학교

---

<접근 방법>

1. 우선, 표에 주어진 정보를 가지고 있어야 하므로, info라는 큰 dictionary 안에 "해당학생번호-set(좋아하는 학생들)"의 정보를 담는다.
   또한, 학생들은 순서대로 배치할 것이므로 sequence라는 list에 학생을 순서대로 담아놓는다.
2. 위의 sequence에 담은 학생들 순서대로,
   각 칸에 배치했을 경우, 좋아하는 학생들의 수, 빈칸의 수를 세어 temp라는 하나의 임시 리스트에 정보를 저장해둔다.
3. temp를 본문에 쓰여 있는 기준 순서대로, 좋아하는 학생들 수, 빈칸 수, 행, 열을 기준으로 정렬한다.
4. 가장 부합하는 자리(temp[0][0], temp[0][1])에 학생을 배치한다. (모든 학생 과정 동일)
5. 모두 배치가 끝났다면 만족도를 계산하기 위해 각 칸을 돌며 좋아하는 학생들 수를 세어 더한다.

N = int(input())
arr = [[0]*N for _ in range(N)]
info = dict()   # "해당 학생 - 좋아하는 학생 그룹" 저장
sequence = []   # 학생들 순서
for _ in range(N*N):
    num, st1, st2, st3, st4 = map(int, input().split())
    info[num] = {st1, st2, st3, st4}
    sequence.append(num)

for num in sequence:    # 학생들 순서대로 배치
    temp = []   # (행, 열, 좋아하는 친구 수, 빈칸 수)를 담을 임의의 리스트
    for i in range(N):
        for j in range(N):
            if arr[i][j]: continue
            friend, blank = 0, 0
            for di, dj in ((-1, 0), (0, 1), (1, 0), (0, -1)):
                ni = i + di
                nj = j + dj
                if 0<=ni<N and 0<=nj<N:
                    if arr[ni][nj] in info[num]:	# 주변이 친한 친구라면
                        friend += 1
                    elif not arr[ni][nj]:	# 주변이 빈 칸이라면
                        blank += 1
            temp.append((i, j, friend, blank))

    # 본문의 기준대로 정렬 후 배치
    temp.sort(key=lambda x: (-x[2], -x[3], x[0], x[1]))
    arr[temp[0][0]][temp[0][1]] = num

satisfaction = 0
score = {0: 0, 1: 1, 2: 10, 3: 100, 4: 1000}    # 점수표
for i in range(N):
    for j in range(N):
        count = 0
        for di, dj in ((-1, 0), (0, 1), (1, 0), (0, -1)):
            ni = i + di
            nj = j + dj
            if 0<=ni<N and 0<=nj<N and arr[ni][nj] in info[arr[i][j]]:
                count += 1
        satisfaction += score[count]
print(satisfaction)

예제2의 배치

이해가 되지 않는 부분이 있으면 질문 주세요. 감사합니다.