[백준] 21608. 상어 초등학교

 

21608번: 상어 초등학교

삼성전자 2021 상반기 문제이다.

 

input data를 리스트로 한 번에 받아 준 뒤, for 문으로 리스트를 순회하며 {학생:(좋아하는 친구)} 형식으로 dictionary에 저장하고 find_desk() 함수를 돌아가며 자리를 정해줬다. dictionary에 자료를 저장한 이유는 뒤에 만족도 조사 시에 편리하게 확인하기 위해서 이다.

 

find_desk() 함수는 완전 탐색으로 모든 곳을 확인하며, 비어있는 책상에서 delta 변수로 상하좌우를 확인해서 주변에 좋아하는 친구와 빈 책상을 모두 저장해주었다. 책상 마다 좋아하는 친구를 기준으로 좋아하는 친구가 가장 많으면 바로 해당 자리와 값들을 저장해주었고, 좋아하는 친구의 수가 이전과 같다면 빈자리 개수가 더 많으면 값을 저장해준다. 세 번째 조건은 책상을 왼쪽상단부터 탐색하므로 자연스럽게 충족된다. 탐색이 끝나면 저장된 열, 행 값을 리턴하여 학생을 자리에 앉힌다.

 

그 뒤 똑같이 모든 책상의 상하좌우를 확인해가며 만족도를 저장하면 된다.

# 비어 있는 칸 중에 좋아하는 학생이 인접한 칸에 가장 많은 칸
# 여러 개이면 비어있는 칸이 가장 많은 칸
# 여러개이면 행의 번호가 가장 작은 칸, 그러한 칸도 여러 개 이면 열의 변호가 작은 칸
n = int(input())

dy = [1, -1, 0, 0]
dx = [0, 0, 1, -1]


def find_desk(person):
    max_friend = -1
    max_empty = -1
    person_r = -1
    person_c = -1

    for i in range(n):
        for j in range(n):
            empty_desk = 0
            love_friend = 0
            if not desk[i][j]:
                for k in range(4):
                    ny = i + dy[k]
                    nx = j + dx[k]
                    if 0 <= ny < n and 0 <= nx < n:
                        if desk[ny][nx] in students[person]:
                            love_friend += 1
                        if not desk[ny][nx]:
                            empty_desk += 1
                if max_friend == love_friend:
                    if max_empty < empty_desk:
                        person_r = i
                        person_c = j
                        max_friend = love_friend
                        max_empty = empty_desk
                elif max_friend < love_friend:
                    person_r = i
                    person_c = j
                    max_friend = love_friend
                    max_empty = empty_desk
    return person_r, person_c


input_students = [list(map(int, input().split())) for _ in range(n*n)]
desk = [[0]*n for _ in range(n)]
students = {}
for student in input_students:
    students[student[0]] = set(student[1:])
    y, x = find_desk(student[0])
    desk[y][x] = student[0]

ans = 0

for i in range(n):
    for j in range(n):
        temp = 0
        for k in range(4):
            ny = i + dy[k]
            nx = j + dx[k]
            if 0 <= ny < n and 0 <= nx < n and (desk[ny][nx] in students[desk[i][j]]):
                temp += 1
        if temp == 1:
            ans += 1
        elif temp == 2:
            ans += 10
        elif temp == 3:
            ans += 100
        elif temp == 4:
            ans += 1000
print(ans)