[백준] 21609번 : 상어 초등학교

21608번: 상어 초등학교

21608번: 상어 초등학교

🤔 문제분석

문제만 잘 이해하고 접근했다면 쉽게 풀 수 있는 문제이다. 조건에 따라서 첫번째 연산까지만 할지 두번째 연산까지만 할지 세번째 연산까지만 할지 분기시킨다. 필자는 첫번째 연산, 두번째 연산이 배열의 길이가 1 초과인경우 연산을 추가로 할것인지 분기를 시켰다. 그리고 각 조건에 맞는 결과를 얻기위해 딕셔너리를 사용하였고 딕셔너리를 배열로 전환한뒤 주어진 조건에 따라서 정렬해서 문제를 해결하였습니다.

💻 코드

import sys
from collections import defaultdict

input = sys.stdin.readline
N = int(input())
student_like = [set() for _ in range(N*N + 1)]
order_student = []

for _ in range(N*N):
    temp = list(map(int, input().split()))
    order_student.append(temp[0])
    for t in temp[1:]:
        student_like[temp[0]].add(t)
        
room = [[0 for _ in range(N)] for _ in range(N)]

def is_near_by(y1, x1, y2, x2):
    return 1 == (abs(y1-y2) + abs(x1-x2))

def get_bigest(near_dict):
    temp = []
    for key in near_dict:
        temp.append((near_dict[key], key[0], key[1]))
    
    temp.sort(reverse=True)
    
    result = []
    for t in temp:
        if temp[0][0] != t[0]:
            break
        
        if room[t[1]][t[2]] == 0:
            result.append((t[1], t[2]))

    return result

def first(likedstudent):
    queue = []
    near_dict = defaultdict(int)
    # 내가 좋아하는 학생찾기
    for i in range(N):
        for j in range(N):
            near_dict[(i, j)] = 0
            if room[i][j] in likedstudent:
                queue.append((i, j))

    # 가장 인접한 칸 찾기
    for i, j in queue:
        for i1 in range(N):
            for j1 in range(N):
                if is_near_by(i, j, i1, j1) and room[i1][j1] == 0:
                    near_dict[(i1, j1)] += 1
    
    return get_bigest(near_dict)

def second(queue):
    near_dict = defaultdict(int)
    
    for i, j in queue:
        near_dict[(i, j)] = 0
        for i1 in range(N):
            for j1 in range(N):
                if is_near_by(i, j, i1, j1) and room[i1][j1] == 0 and room[i][j] == 0:
                    near_dict[(i, j)] += 1
    
    return get_bigest(near_dict)
    
def third(queue : list):
    queue.sort(key=lambda x:(x[0], x[1]))
    return [queue[0]]
    

for student in order_student:
    queue = first(student_like[student])
    if len(queue) > 1:
        queue = second(queue)
        if len(queue) > 1:
            queue = third(queue)
            
    seat_pos = queue[0]
    room[seat_pos[0]][seat_pos[1]] = student
    
ans = 0

def get_score(like_cnt):
    if like_cnt == 0:
        return 0
    elif like_cnt == 1:
        return 1
    elif like_cnt == 2:
        return 10
    elif like_cnt == 3:
        return 100
    else:
        return 1000
    
for i in range(N):
    for j in range(N):
        student = room[i][j]
        like_cnt = 0
        for i1 in range(N):
            for j1 in range(N):
                if is_near_by(i, j, i1, j1) and room[i1][j1] in student_like[student]:
                    like_cnt += 1
    
        ans += get_score(like_cnt)
            
print(ans)

🎯 피드백 및 개선사항

구현문제는 주어진 조건을 자세히 살펴보아야 처음에 문제를 어떻게 접근해야할지 보이는것 같습니다.