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

문제

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

소스코드

import sys
if __name__ == "__main__":
    n = int(input())
    arr = [[0] * n for _ in range(n)]
    students = [list(map(int,input().split())) for _ in range(n*n)]

    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    
    
    for s in range(n*n):
        student = students[s]
        tmp = []
        for i in range(n):
            for j in range(n):
                if arr[i][j] == 0:
                    friend = 0
                    empty = 0
                    for k in range(4):
                        x = i + dx[k]
                        y = j + dy[k]
                        if 0<=x<n and 0<=y<n:
                            if arr[x][y] in student[1:]:
                                friend +=1
                            if arr[x][y] == 0:
                                empty +=1
                    tmp.append([friend,empty,i,j])
        tmp.sort(key = lambda x: (-x[0],-x[1],x[2],x[3]))
        arr[tmp[0][2]][tmp[0][3]] = student[0]

    students.sort(key = lambda x:x[0])
    total = 0
    for i in range(n):
        for j in range(n):
            cnt = 0
            for k in range(4):
                x = i + dx[k]
                y = j + dy[k]
                if 0<=x<n and 0<=y<n:
                    if arr[x][y] in students[arr[i][j]-1][1:]:
                        cnt +=1
            if cnt > 0:
                total += 10 ** (cnt -1)
    print(total)

설명

구현과 단순 BFS 문제였다.

1. 학생 배치

• 입력 받은 순서대로 배치
• 빈 칸중에 상하좌우 선호하는 친구가 있는지 확인
• 빈 칸중에 상하좌우 빈칸이 몇개인지 확인
• 가능한 칸의 (친구, 빈칸, 행, 열)을 리스트에 넣기
• 한 학생이 가능한 모든 경우의 수를 체크한 후 (친구 큰값, 빈칸 큰값, 행 작은 값, 열 작은값)순으로 정렬한다.(문제에 주어진 조건을 한번에 체크해주기)
• 첫번째 값이 해당 학생의 자리이다.
• 이 과정의 포인트는 공백과, 친구수, 행,열을 모두 다 리스트에 넣어주고 한번에 정렬해서 0번째 값을 고르는 것

2. 학생 만족도 체크

• 입력받은 학생 배열을 0번째 인덱스 기준으로 오름차순 정렬하기
• 상하좌우 선호하는 친구 있는지 확인해서 몇명인지 체크해주기
• 최종값을 더해주기