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

문제

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

21608번: 상어 초등학교

---

문제 요약

N × N 크기의 교실에 조건에 맞게 학생들을 배치하고 그들의 만족도를 출력한다.

 

조건

1. 비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다.

2. 1을 만족하는 칸이 여러 개이면, 인접한 칸 중에서 비어있는 칸이 가장 맣은 칸으로 자리를 정한다.

3. 2를 만족하는 칸도 여러 개인 경우에는 행의 번호가 가장 작은 칸으로, 그러한 칸도 여러 개이면 열의 번호가 가장 작은 칸으로 자리를 정한다.

---

코드

def sit(num, friends):
    b_i = b_j = -1
    # 가장 적합한 인덱스

    max_fnum = 0
    max_enum = 0
    # 가장 적합한 인덱스의 친한 친구 수와 빈칸 수
    check = False

    for i in range(N):
        for j in range(N):
            if arr[i][j] == 0:
            # arr가 비었다면

                # 처음 빈 자리를 발견하면 그곳을 초기 값으로 설정
                if not check:
                    b_i = i
                    b_j = j
                    check = True

                f_num = e_num = 0
                # f_num은 인접한 곳에 있는 좋아하는 친구 수
                # e_num은 인접한 곳에 있는 빈 자리 수

                # 인접한 네 방향의 인덱스 검사
                for d in range(4):
                    ni = i + dx[d]
                    nj = j + dy[d]

                    # 네 방향의 인덱스가 자리 배치도 범위 안에 있어야 함
                    if 0 <= ni < N and 0 <= nj < N:
                        if arr[ni][nj] == 0: # 비었다면
                            e_num += 1
                        elif arr[ni][nj] in friends: # 좋아하는 친구라면
                            f_num += 1

                if f_num > max_fnum: 
                # 이전까지 인접한 곳에 있는 좋아하는 친구 수보다 많으면 업데이트
                    max_fnum = f_num
                    max_enum = e_num
                    b_i = i
                    b_j = j
                elif f_num == max_fnum and e_num > max_enum:
                # 좋아하는 친구 수가 같고 빈 자리가 더 많으면 업데이트
                    max_fnum = f_num
                    max_enum = e_num
                    b_i = i
                    b_j = j

    # 위 과정이 끝나고 가장 적합한 자리에 번호 넣기
    arr[b_i][b_j] = num

# 2차원 배열에서의 원하는 값의 인덱스를 반환하는 함수
def find(value):
    for row_idx, row in enumerate(arr):
        for col_idx, element in enumerate(row):
            if element == value:
                return row_idx, col_idx
    return None

# 상 하 좌 우를 나타내는 방향
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# 교실 크기 N * N (학생 수)
N = int(input())

# 입력 받은 학생 번호와 그들이 좋아하는 4명의 학생 번호
data = [list(map(int, input().split())) for _ in range(N ** 2)]

# N * N 자리 배치도 구현
arr = [[0] * N for _ in range(N)]

# 입력 받은 학생 순서대로 규칙에 맞게 자리 구하기
for n in range(N ** 2):
    sit(data[n][0], data[n][1:])

# 만족도
res = 0

for n in range(N ** 2):
    cnt = 0 # 학생 n의 인접한 자리에 존재하는 좋아하는 학생 수
    num = data[n][0] # 학생 번호
    friend = data[n][1:] # 학생이 좋아하는 학생 리스트
    i, j = find(num) # 학생의 자리 인덱스 찾기

    # 학생의 인접한 인덱스에 좋아하는 학생이 몇 명 존재하는지 확인
    for d in range(4):
        ni = i + dx[d]
        nj = j + dy[d]
        if 0 <= ni < N and 0 <= nj < N:
            if arr[ni][nj] in friend:
                cnt += 1
    
    # 인접한 칸에 앉은 좋아하는 학생 수에 따른 만족도
    if cnt == 1:
        res += 1
    elif cnt == 2:
        res += 10
    elif cnt == 3:
        res += 100
    elif cnt == 4:
        res += 1000

print(res)

---

코드 설명

1. 입력 받은 학생들의 순서대로 sit함수를 통해 조건에 맞게 자리에 배치한다.

+ 3번째 조건은 sit함수가 어짜피 0행, 0열의 빈 자리부터 검사하므로 굳이 처리할 필요가 없다.

 

2. 자리에 모두 앉았다면, 각 학생들의 인접한 인덱스에 좋아하는 학생이 몇 명 존재하는지 확인하고 만족도를 출력한다.

 

+ 인접한 인덱스에 좋아하는 학생 수에 따른 만족도

0명: 0점

1명: 1점

2명: 10점

3명: 100점

4명: 1000점