[Python] 백준 21608번 - 상어 초등학교

 

구현 자체는 쉬웠지만 엣지케이스를 통과하지 못했다

 

틀린 이유 

1. 오름차순 소팅해야하는데 내림차순으로 했던 경우

2. min 값을 비교할 때, 기준값을 0 으로 잘못 설정 

3. 함수 분리를 더 꼼꼼히 해야할 것 같다 

---

# 1. 비어있는 칸 중에서 좋아하는 학생이 인접한 칸이 가장 많은 곳
def likes():
    like_cnt = []

    for i in range(n):
        for j in range(n):
            if seats[i][j] == 0:
                cnt = 0
                for dx, dy in zip(go_x, go_y):
                    nx = dx + i
                    ny = dy + j
                    if 0 <= nx < n and 0 <= ny < n and seats[nx][ny] in orders:
                        cnt += 1
                like_cnt.append((cnt, (i, j)))

    max_cnt = max(like_cnt)[0]
    cords = [c[1] for c in like_cnt if c[0] == max_cnt]
    return cords


# 2. 1 여러개이면 인접 칸 중에서 비어있는 칸이 가장 많은 곳으로 자리를 정함
def chk_empty(candidates):
    empty_dict = {}

    for s_coord in candidates:
        cnt = 0
        x, y = s_coord[0], s_coord[1]
        for dx, dy in zip(go_x, go_y):
            nx = dx + x
            ny = dy + y
            if 0 <= nx < n and 0 <= ny < n and seats[nx][ny] == 0:
                cnt += 1
        if cnt in empty_dict:
            empty_dict[cnt].append(s_coord)
        else:
            empty_dict[cnt] = [s_coord]

    empty_list = dict(sorted(empty_dict.items()))
    return empty_list.get(max(empty_list))


# 3. 2 여러개이면 행의 번호가 가장 작은 칸으로 자리를 정함
def small_rows(candidates):
    min_row = min(candidates)[0]
    row_list = []

    for cords in candidates:
        if cords[0] == min_row:
            row_list.append(cords)

    return row_list


# 4. 2 여러개이면 열의 번호가 가장 작은 칸으로 자리를 정함
def small_cols(candidates):
    min_col = 100000
    for cords in candidates:
        min_col = min(min_col, cords[1])

    for cords in candidates:
        if cords[1] == min_col:
            return cords[0], cords[1]


# 만족도 계산
def calc_score():
    score = 0
    new_orders = {sv[0]: sv[1:] for sv in students}
    score_v = [0, 1, 10, 100, 1000]
    for i in range(n):
        for j in range(n):
            cnt = 0
            s_num = seats[i][j]
            s_orders = new_orders.get(s_num)
            for dx, dy in zip(go_x, go_y):
                nx = dx + i
                ny = dy + j
                if 0 <= nx < n and 0 <= ny < n and seats[nx][ny] in s_orders:
                    cnt += 1
            score += score_v[cnt]

    return score


if __name__ == '__main__':
    n = int(input())
    seats = [[0 for _ in range(n)] for _ in range(n)]
    students = []
    go_x = [0, 0, 1, -1]
    go_y = [1, -1, 0, 0]

    for _ in range(n*n):
        students.append(list(map(int, input().split())))

    for s_info in students:
        x, y = 0, 0
        s, orders = s_info[0], s_info[1:]

        like_seats = likes()

        if len(like_seats) > 1:
            empty_seats = chk_empty(like_seats)
            if len(empty_seats) > 1:
                row_seats = small_rows(empty_seats)
                if len(row_seats) > 1:
                    x, y = small_cols(row_seats)
                else:
                    x, y = row_seats[0][0], row_seats[0][1]
            else:
                x, y = empty_seats[0][0], empty_seats[0][1]
        else:
            x, y = like_seats[0][0], like_seats[0][1]

        seats[x][y] = s

    print(calc_score())