BOJ - 상어 초등학교 21608번 (python)

❓ 문제 - 백준 상어 초등학교 21608번 - python 풀이법

출처 

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

21608번: 상어 초등학교

 

 

📝 문제해결법

1. 문제 풀이의 핵심은 문제 조건에 맞게 잘 구현하기

2. 문제의 데이터 제한 N의 범위가 3 <= N <= 20 이므로 N*N 의 행과 열에서 모두 조건에 해당되는지 파악하여 자리에 위치시켜야함

3. 구현 소스 코드 흐름

• 마지막에 학생들이 인접한 지역에 좋아하는 학생들이랑 앉았는지 확인하기 위하여 like_room 리스트를 통해 각 학생 인덱스에 맞는 좋아하는 사람을 저장
• p(n*n)명 모두 확인해야함 -> 각 학생 인덱스와 그 학생이 좋아하는 사람을 입력받고 like_room 리스트에 append
• 만약 처음 학생의 자리 배치 경우 1, 2, 3 조건에 해당하는 자리는 무조건 (1,1)이므로 위치 시킴
• 모든 행과 열(n*n) 범위를 돌면서 상하좌우 살펴 3개의 조건에 해당되는 최적 자리를 선정함
• 상하좌우 돌 때, 리스트 인덱스 범위 벗어나면 continue 
• 모든 행과 열 (n*n) 범위를 돌면서 해당 자리에서 인접한 곳에 좋아하는 학생이 있을 때 sum_like, 인접한 곳이 빈 경우일 때 sum_empty를 1증가 시킴
• 상하좌우 다 살폈을 때 temp 리스트에 sum_like, sum_empty, (i,j => 해당 행,열값) append 해줌
•  모든 행과 열(n*n) 범위 살핀 후, temp 리스트를 sort 해줘서 조건에 맞게 sum_like 값이 많은 때, 그 후 sum_like 값이 동일하다면 sum_empty 값이 많은 때,  또한 sum_empty 값도 동일하다면 행 값이 작을 때, 행 값도 동일하다면 열 값이 작을 때 순으로 정렬
• 정렬 후 가장 첫 번째 있는 값의 행, 열값을 최적 위치로 선정하기 위하여 classroom 리스트의 해당 행, 열에 학생 번호로 변경
• 마지막으로  classroom에 최적 자리로 선정된 학생들 하나하나 인접 지역에 얼마나 좋아하는 학생이 배치되었는지 확인하여 학생의 만족도를  계산

 

 

💻 소스코드

# 상어초등학교 - BOJ 21609
# 구현 
import sys

input = sys.stdin.readline

n = int(input())
p = n * n
classroom = [[0] * n for _ in range(n)]
like_room = [[] for _ in range(p+1)]
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

for _ in range(p):
    array = list(map(int, input().split()))
    like = array[1:]
    like_room[array[0]] = like
    if p == 0:
        classroom[1][1] = array[0]
        continue
    temp = []
    for i in range(n):
        for j in range(n):
            sum_like, sum_empty = 0, 0
            if classroom[i][j] != 0:
                continue
            for k in range(4):
                nx = i + dx[k]
                ny = j + dy[k]
                if nx < 0 or nx > n-1 or ny < 0 or ny > n-1:
                    continue
                if classroom[nx][ny] in like:
                    sum_like += 1
                if classroom[nx][ny] == 0:
                    sum_empty += 1
            temp.append((sum_like, sum_empty, (i, j)))
    temp.sort(key=lambda x:(-x[0], -x[1], x[2]))

    classroom[temp[0][2][0]][temp[0][2][1]] = array[0]

sum_answer = 0


for i in range(n):
    for j in range(n):
        answer = 0
        for k in range(4):
            nx = i + dx[k]
            ny = j + dy[k]
            if nx < 0 or nx > n - 1 or ny < 0 or ny > n - 1:
                continue
            if classroom[nx][ny] in like_room[classroom[i][j]]:
                answer += 1
                continue
        if answer != 0:
            sum_answer += (10 ** (answer - 1))


print(sum_answer)

 

 

🤷 느낀점

구현의 핵심은 일단 문제의 주어진 조건에 해당하는 부분을 다 체크하고, 디테일한 부분까지 신경써야할 것 같다.

구현력을 높이기 위해서 다른 구현 알고리즘 문제를 풀 때, 노트에 문제를 풀기위한 전체적인 흐름, 디테일한 부분까지 다 정리 후에 소스코드를 구현해야겠다고 느꼈다.