[백준 21608] 상어 초등학교 (Silver 1)

문제

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

접근

1. 각 학생마다 좋아하는 학생들의 정보를 딕셔너리로 저장한다.
2. 그 다음 각각의 좌표마다 1, 2번의 조건을 체크 해준다. 그리고 체크 결과를 리스트에 저장한다.
3. 모든 맵을 다 돌았으면 체크 결과를 담은 리스트를 정렬한다. 이 때 정렬 우선 순위는 좋아하는 사람이 많은 순 -> 주변에 빈 자리가 많은 순 -> r의 좌표가 작은 순 -> c의 좌표가 작은 순으로 정렬한다. 정렬 이후 맨 첫번째 원소의 (r,c)를 가져와 그 좌표에 현재 학생 번호로 값을 준다.
4. 맵이 다 채워졌으면 다시 한번 맵을 완전탐색하고 만족도를 구한다.

Code

import sys
from collections import defaultdict

n = int(sys.stdin.readline())
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
mapping = defaultdict(list)
maps = [[0] * n for _ in range(n)]
answer = 0


def check_conditon(y, x, student):
    loved, checked = 0, 0
    for i in range(4):
        cy, cx = y + dy[i], x + dx[i]

        if cx < 0 or cx >= n or cy < 0 or cy >= n:
            continue
        if not maps[cy][cx]:
            checked += 1

        if maps[cy][cx] in mapping[student]:
            loved += 1

    return (loved, checked, y, x)


def check_satisfaction(y, x, student):
    loved = 0
    for i in range(4):
        cy, cx = y + dy[i], x + dx[i]

        if cx < 0 or cx >= n or cy < 0 or cy >= n:
            continue

        if maps[cy][cx] in mapping[student]:
            loved += 1

    if not loved:
        return 0
    elif loved == 1:
        return 1
    elif loved == 2:
        return 10
    elif loved == 3:
        return 100
    else:
        return 1000


for _ in range(n * n):
    arr = list(map(int, sys.stdin.readline().split()))
    for i in arr[1:]:
        mapping[arr[0]].append(i)

for student in list(mapping):
    placeInfo = []
    for y in range(n):
        for x in range(n):
            if not maps[y][x]:
                placeInfo.append(check_conditon(y, x, student))

    placeInfo = sorted(placeInfo, key=lambda x: (-x[0], -x[1], x[2], x[3]))[0]
    maps[placeInfo[2]][placeInfo[3]] = student

for y in range(n):
    for x in range(n):
        answer += check_satisfaction(y, x, maps[y][x])
print(answer)

여담

삼성이 좋아하는 상어 시리즈. 상어 문제하면 떠오르는 악랄한 구현 문제들에 비해 이건 좀 쉬운 편에 속했다.