[백준 baekjoon] 백준 21608번 상어 초등학교 by 파이썬(Python) : 구현

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

21608번: 상어 초등학교

 

난이도

골드5

 

 

문제 설명

• n*n크기의 교실에 n^2 명의 학생이 있다.
• 학생들을 일정한 조건에 따라 교실에 배치해야한다.

    조건

1. 비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다.
2. 1을 만족하는 칸이 여러 개이면, 인접한 칸 중에서 비어있는 칸이 가장 많은 칸으로 자리를 정한다.
3. 2를 만족하는 칸도 여러 개인 경우에는 행의 번호가 가장 작은 칸으로, 그러한 칸도 여러 개이면 열의 번호가 가장 작은 칸으로 자리를 정한다.

• 모든 학생의 만족도 합을 구해 출력 한다.
• ㄴ 만족도는 옆에 앉은 학생이 좋아하는 학생 수 에 따라 결정된다 0인경우 0 , 1명인경우 1 ,2명인경우 10, 3 : 100, 4 : 1000이다.

 

 

접근법

• 직접 조건에 따라 구현하면서 교실을 완전 탐색해야한다.
• 크게는 학생 수만큼 반복문을 돌리고 그 안에서 모든 교실의 좌석을 탐색하여 조건에 부합한지를 확인해야한다.
• 해당 교실 자리의 주변에 좋아하는 학생 수(like) , 비어 있는 칸(blank) 을 세어 임시 배열(arr)에 해당 자리 좌표와 함께 저장해준다. 
• 임시배열 arr를 조건에 맞춰 like, blank순으로 내림차순 정렬해주고, 좌표값은 최소가 되도록 오름차순으로 정렬해준다.
• 초기화된 좌석 배열 (temp)에 정렬된 arr중 가장 앞의 값이 조건에 가장 부합하는 좌석임으로 학생을 해당 좌표 좌석배열에 저장해준다.
• 학생들의 교실 좌석 배정이 끝나면 점수를 계산하기 위해 학생 입력순서를 학생번호 순으로 정렬해준다.
• 교실 좌석을 모두 확인하면서 해당 학생 주변에 좋아하는 학생의 수를 센 후 만족도 점수를 더해준다.
• 모든 학생의 점수가 더해지면 총 만족도 점수를 출력해준다.

 

 

코드

room = int(input())
temp = [[0]*room for _ in range(room)] #좌석 표 초기화
students = []
dx = [-1, 1, 0, 0]
dy = [0, 0 ,-1, 1]
for _ in range(room*room):
    a = list(map(int, input().split()))
    students.append(a)

for s in range(room**2): #학생 수 만큼 탐색
    student = students[s]
    arr = []
    for x in range(room): #모든 좌석 탐색
        for y in range(room):
            if temp[x][y] == 0:
                like = 0
                blank = 0
                for r in range(4): # 주변 칸 탐색
                    nx = dx[r] + x
                    ny = dy[r] + y

                    if 0<=nx<room and 0<=ny<room:
                        if temp[nx][ny] in student[1:]: #좋아하는 사람이 인접한 경우 카운팅
                            like += 1
                        if temp[nx][ny] == 0:  #빈칸이 있는 경우 카운팅
                            blank += 1
                arr.append([like, blank, x, y])
    arr.sort(key=lambda x:(-x[0], -x[1], x[2],x[3])) # 조건에 따라 정렬
    temp[arr[0][2]][arr[0][3]] = student[0]

result = 0 
students.sort() 
for i in range(room):
    for j in range(room):
        grade = 0 
        for r in range(4):
            nx = dx[r] + i
            ny = dy[r] + j
            if 0<=nx<room and 0<=ny<room:
                if temp[nx][ny] in students[temp[i][j]-1]: #sort해주어 해당 좌표값-1이 학생 번호와 동일
                    grade += 1
        
        if grade != 0:
            result += 10**(grade-1)

print(result)

 

---

구현 ?

https://h-castle.tistory.com/entry/%EA%B5%AC%ED%98%84-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B5%AC%ED%98%84-Implementation

[구현] 알고리즘 - 구현 (Implementation)