백준 21608 상어 초등학교 (파이썬)

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

21608번: 상어 초등학교

1. 학생의 번호와 좋아하는 학생의 번호를 a에 딕셔너리로 저장한다.

   c는 자리에 학생이 있는지를 체크한다.

2. 딕셔너리에서 하나씩 불러와서 자리를 배정한다.

   해당 좌표에서의 c값이 0이면 인접한 칸에 좋아하는 학생이 얼마나 있는지 cnt에 저장한다.

   cnt가 0보다 크면 1번 규칙을 만족하는 자리 후보 리스트인 seat_list1에 cnt와 좌표 순으로 저장한다.

3. seat_list1에 값이 있으면 우선 정렬한 후, 값이 하나 밖에 없거나 만족하는 칸이 여러개가 아니면 자리를 배정한다

4. 1번 규칙을 만족하지 못하면 인접한 칸에서 비어있는 칸을 탐색한다.

   seat_list1에 값이 없었으면 비어있는 칸이 가장 많은 칸을 찾는다.

5. seat_list1에 값이 있는 경우면 규칙 1을 만족하는 칸이 여러개인 경우다.

   규칙 1을 만족하는 자리 중에서 인접한 빈 칸이 많은 것을 찾아야 하므로

   좋아하는 학생의 자리가 가장 많은 자리만 있도록 seat_list1를 갱신한다.

6. 빈칸의 개수를 cnt에 저장하고 seat_list2에 cnt와 좌표 순으로 저장한다.

   seat_list2 값이 하나밖에 없거나 규칙을 만족하는 칸이 여러개가 아니면 자리를 배정한다.

7. 규칙 2를 만족하는 칸도 여러 개이면 seat_list2 값을 하나씩 불러온다.

   seat_list2는 이미 정렬했기 때문에 만족하는 칸 개수의 최대값을 읽게되면, 그 때의 자리에 배정한다.

8. 조건대로 만족도를 구한후 출력한다

import sys

input = sys.stdin.readline
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

n = int(input())
c = [[0]*n for _ in range(n)]

a = {}
for _ in range(n**2):
    num = []
    for i, s in enumerate(input().split()):
        if i == 0:
            temp = s
        else:
            num.append(s)
    a[temp] = num

for k, v in a.items():
    seat_list1 = []
    for i in range(n):
        for j in range(n):
            if c[i][j] == 0:
                cnt = 0
                for d in range(4):
                    ni = i + dx[d]
                    nj = j + dy[d]
                    if not 0 <= ni < n or not 0 <= nj < n:
                        continue
                    if c[ni][nj] == 0:
                        continue
                    if c[ni][nj] in v:
                        cnt += 1
                if cnt > 0:
                    seat_list1.append([cnt, i, j])
    if seat_list1:
        seat_list1 = sorted(seat_list1)
        if len(seat_list1) == 1 or (len(seat_list1) > 1 and seat_list1[-1][0] != seat_list1[-2][0]):
            x, y = seat_list1[-1][1:]
            c[x][y] = k
            continue

    seat_list2 = []
    if not seat_list1:
        for i in range(n):
            for j in range(n):
                if c[i][j] == 0:
                    cnt = 0
                    for d in range(4):
                        ni = i + dx[d]
                        nj = j + dy[d]
                        if not 0 <= ni < n or not 0 <= nj < n:
                            continue
                        if c[ni][nj] != 0:
                            continue
                        cnt += 1
                    seat_list2.append([cnt, i, j])
        seat_list2 = sorted(seat_list2)
        if len(seat_list2) == 1 or (len(seat_list2) > 1 and seat_list2[-1][0] != seat_list2[-2][0]):
            x, y = seat_list2[-1][1:]
            c[x][y] = k
            continue
    else:
        max_n = max(seat_list1)[0]
        for i, s in enumerate(seat_list1):
            if s[0] == max_n:
                seat_list1 = seat_list1[i:]
                break
        for s in seat_list1:
            x, y = s[1:]
            cnt = 0
            for d in range(4):
                nx = x + dx[d]
                ny = y + dy[d]
                if not 0 <= nx < n or not 0 <= ny < n:
                    continue
                if c[nx][ny] != 0:
                    continue
                cnt += 1
            seat_list2.append([cnt, x, y])
        seat_list2 = sorted(seat_list2)
        if len(seat_list2) == 1 or (len(seat_list2) > 1 and seat_list2[-1][0] != seat_list2[-2][0]):
            x, y = sorted(seat_list2)[-1][1:]
            c[x][y] = k
            continue

    max_n = max(seat_list2)[0]
    for s in seat_list2:
        if s[0] == max_n:
            x, y = s[1:]
            c[x][y] = k
            break

ans = 0
for i in range(n):
    for j in range(n):
        cnt = 0
        for k in range(4):
            ni = i + dx[k]
            nj = j + dy[k]
            if not 0 <= ni < n or not 0 <= nj < n:
                continue
            if c[ni][nj] in a[c[i][j]]:
                cnt += 1
        if cnt > 0:
            ans += 10 ** (cnt - 1)
print(ans)