142. [삼성기출38]Python 백준 21608 상어 초등학교

안녕하세요 코딩하는 덕구입니다.

파이썬 백준 21608 상어 초등학교 입니다.

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

21608번: 상어 초등학교

 

문제 접근

모든 자리를 순회하며 만약 빈 자리라면 해당 자리 좌표, 인접한 위치에 좋아하는 친구의 수, 빈 자리의 수 를 후보 리스트에 추가했습니다.

순회가 끝나면 후보 리스트를 인접한 위치의 좋아하는 친구의 수, 인접한 위치의 빈자리의 수, 행, 열 우선순위로 정렬한 후

리스트의 0번 자료를 뽑아 자리를 배정했습니다.

 

Python 정답 코드

백준 21608 상어 초등학교 코드입니다. 설명은 아래에 있습니다.

 

N = int(input())
student = [list(map(int, input().split())) for _ in range(N**2)]
board = [[0 for _ in range(N)] for _ in range(N)]
student_fav = [[] for _ in range(N**2 + 1)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
ans = 0

def find_adjacent_fav_and_empty_num(i, j, fav_friend):
    fav_num = 0
    empty_num = 0
    for d in range(4):
        nx, ny = i + dx[d], j + dy[d]
        if 0 <= nx < N and 0 <= ny < N:
            if board[nx][ny] in fav_friend:
                fav_num += 1
            if board[nx][ny] == 0:
                empty_num += 1

    return fav_num, empty_num

def solve():
    global ans
    for s in student:
        candidate = []
        for i in range(N):
            for j in range(N):
                if board[i][j] == 0:
                    adjacent_fav_num, adjacent_empty_num = find_adjacent_fav_and_empty_num(i, j, s[1:])
                    candidate.append([i, j, adjacent_empty_num, adjacent_fav_num])

        candidate.sort(key=lambda x:[-x[3], -x[2], x[0], x[1]])
        x, y, _, _ = candidate[0]
        board[x][y] = s[0]
        student_fav[s[0]] = s[1:]


    for i in range(N):
        for j in range(N):
            adjacent_fav_num, _ = find_adjacent_fav_and_empty_num(i, j, student_fav[board[i][j]])
            ans += 10**adjacent_fav_num//10
    return ans

print(solve())

 

Python 코드 설명

1. 먼저 student for 문은 자리 배정 학생 순서대로 접근하여 자리를 배정합니다.

먼저 후보 리스트를 만들고 모든 자리를 순회합니다.

빈자리라면, 자리 결정에 필요한 요소들과 함께 해당 자리의 좌표까지 후보 리스트에 추가합니다.

이후 자리 결정 기준에 맞게 정렬 후 맨 앞 데이터만 뽑아 자리를 배정합니다.

 

2. 하단의 2중 for문은 학생의 점수를 계산해서 ans에 더합니다.

def solve():
    global ans
    for s in student:
        candidate = []
        for i in range(N):
            for j in range(N):
                if board[i][j] == 0:
                    adjacent_fav_num, adjacent_empty_num = find_adjacent_fav_and_empty_num(i, j, s[1:])
                    candidate.append([i, j, adjacent_empty_num, adjacent_fav_num])

        candidate.sort(key=lambda x:[-x[3], -x[2], x[0], x[1]])
        x, y, _, _ = candidate[0]
        board[x][y] = s[0]
        student_fav[s[0]] = s[1:]


    for i in range(N):
        for j in range(N):
            adjacent_fav_num, _ = find_adjacent_fav_and_empty_num(i, j, student_fav[board[i][j]])
            ans += 10**adjacent_fav_num//10
    return ans

print(solve())

 

이 함수는 좌표 주변의 좋아하는 친구의 수와, 빈 자리의 수를 출력합니다.

def find_adjacent_fav_and_empty_num(i, j, fav_friend):
    fav_num = 0
    empty_num = 0
    for d in range(4):
        nx, ny = i + dx[d], j + dy[d]
        if 0 <= nx < N and 0 <= ny < N:
            if board[nx][ny] in fav_friend:
                fav_num += 1
            if board[nx][ny] == 0:
                empty_num += 1

    return fav_num, empty_num

 

백준 21608 상어 초등학교 Python 코드였습니다.

감사합니다.