[백준] 21608번 상어 초등학교 파이썬 풀이

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

21608번: 상어 초등학교

---

1. 접근 방식

• 딕셔너리를 적극 사용하자

학생이 좋아하는 학생들을 담는 survey 딕셔너리, (딕셔너리는 순서가 없으므로) 학생이 입력된 순서를 저장하는 order 딕셔너리, 학생이 앉은 최종 자리를 담는 decided 딕셔너리를 만들었다.

 

 

• 첫 번째 조건: 학생이 좋아하는 학생들과 인접한 칸을 찾는다.

좋아하는 학생이 앉은 위치를 찾을 때 '학생이 앉은 최종 자리를 담는 decided 딕셔너리'를 활용한다. 만약 아직 좋아하는 학생이 자리에 앉지 않았다면, 즉 decided[ 좋아하는 친구 ]가 None이라면 인접한 위치를 찾을 수 없으므로 넘어간다.

반면 좋아하는 친구가 자리에 앉아 있다면, 그 친구와 인접한 칸인 상하좌우를 순회하면서 ① 유효한 위치이고 ② 빈 자리 정보를 저장한다. 이때 좋아하는 학생들과 가장 많이 인접하는 자리를 찾아야 하므로, 각 자리별로 선택된 누적 횟수를 저장해야 한다.

 

문제 지문에서 8번 학생의 경우, 좋아하는 학생들이 1, 9, 3, 4일 때 8번 학생이 앉을 수 있는 자리 후보를 나타낸 그림이다. 위 후보 중에서 8번 학생이 앉을 자리는, 2명의 친구가 접한 (2, 1)이다. 이렇게 인접한 친구 개수(= 누적 횟수)를 저장하는 available 딕셔너리를 만들자.

 

 

• 두 번째 조건: 빈 칸이 가장 많은 칸

첫 번째 조건을 만족하는 위치가 존재할 때와 만족하는 위치가 존재하지 않을 때. 이 2가지를 나누어 생각한다.

전자의 경우엔 첫 번째 조건을 만족하는 각 위치의 인접한 칸(상하좌우)를 순회하면서 비어 있는 칸이 몇 개인지 확인하면 된다.

후자의 경우엔, 상하좌우를 순회하며 빈 칸 개수를 세는 것은 전자와 동일하지만 어떤 위치들을 넣는지가 다르다. 만약 어떤 학생이 좋아하는 학생들이 아직 아무도 자리에 앉지 않았다면, 그 학생은 비어 있는 어떤 자리든 앉을 수 있다. 따라서 모든 빈 자리를 대상으로 순회해야 한다.

 

 

• 세 번째 조건: 가장 작은 행, 그 중에서도 가장 작은 열

이 조건은 두 번째 조건에서 바로 처리할 수 있다. 2번째 조건을 만족하는 위치들을, 다시 행과 열 순서로 정렬하면 되기 때문이다.

 

 

 

2. 정답 코드

import sys

input = sys.stdin.readline

# 좋아하는 학생의 인접한 칸 찾기
def condition1(std):
    available = dict()

    for friend in survey[std]:
        if not decided.get(friend):
            continue

        for adj in adjacent:
            r = decided[friend][0] + adj[0]
            c = decided[friend][1] + adj[1]

            if r < 0 or c < 0 or r >= n or c >= n:
                continue

            if not seats[r][c]:
                if available.get((r, c)):
                    available[(r, c)] += 1
                else:
                    available[(r, c)] = 1

    temp = sorted(list(available.keys()), key=lambda x: available[x], reverse=True)
    return [x for x in temp if available[x] >= available[temp[0]]]

# 빈 칸이 가장 많은 칸
def condition2_and_3(available):
    result = {av: 0 for av in available}

    for av in available:
        for adj in adjacent:
            r = av[0] + adj[0]
            c = av[1] + adj[1]

            if r < 0 or c < 0 or r >= n or c >= n:
                continue

            if not seats[r][c]:
                result[av] += 1

    return sorted(list(result.keys()), key=lambda x: (-result[x], x))

# 학생 만족도
def sum_satisfaction():
    satisfaction = {0: 0, 1:1, 2: 10, 3: 100, 4: 1000}
    result = 0

    for i in range(n**2):
        std = order[i]

        count = 0
        for adj in adjacent:
            r = decided[std][0] + adj[0]
            c = decided[std][1] + adj[1]

            if r < 0 or c < 0 or r >= n or c >= n:
                continue

            for favorite in survey[std]:
                if decided[favorite] == (r, c):
                    count += 1

        result += satisfaction[count]

    return result


## main
n = int(input())
adjacent = [(-1, 0), (1, 0), (0, -1), (0, 1)]

survey = dict() # std: [a, b, c, d], 각 학생별 좋아하는 학생 정보 저장
order = dict() # order: std, 학생이 입력된 순서

seats = [[False] * n for _ in range(n)] # n x n 크기의 교실 (자리에 앉았는지 아닌지 확인)
decided = dict() # std: (r, c) # 학생이 앉은 자리 위치

# 학생들이 좋아하는 친구 설문조사
for i in range(n**2):
    s = list(map(int, input().split()))
    order[i] = s[0]
    survey[s[0]] = s[1:]

# solution
for i in range(n**2):
    std = order[i]

    result1 = condition1(std)

    if len(result1) == 0:
        result1 = [(r, c) for c in range(n) for r in range(n) if not seats[r][c]]

    pos = condition2_and_3(result1)[0]
    seats[pos[0]][pos[1]] = True
    decided[std] = pos

print(sum_satisfaction())