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

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

21608번: 상어 초등학교

 

# 21608 상어 초등학교

# 상 좌 하 우
dr = [-1, 0, 1, 0]
dc = [0, -1, 0, 1]

N = int(input())
likes = [list(map(int, input().split())) for _ in range(N ** 2)]
grounds = [[0] * N for _ in range(N)]

score_help = dict()
# 자리 구하기
for idx in range(N ** 2):
    cur_likes = likes[idx]
    cur_student = cur_likes.pop(0)

    # 좋아하는 학생이 인접
    # 빈 자리가 많아야
    like_student = 0
    empty_seat = 0
    result_r = -1
    result_c = -1

    for r in range(N):
        for c in range(N):
            if grounds[r][c] == 0:
                temp_student = 0
                temp_empty = 0
                for i in range(4):
                    cr = r + dr[i]
                    cc = c + dc[i]
                    if 0 <= cr < N and 0 <= cc < N:
                        if grounds[cr][cc] in cur_likes:
                            temp_student += 1
                        elif grounds[cr][cc] == 0:
                            temp_empty += 1
                if temp_student > like_student:
                    like_student = temp_student
                    empty_seat = temp_empty
                    result_r = r
                    result_c = c
                elif temp_student == like_student and temp_empty > empty_seat:
                    empty_seat = temp_empty
                    result_r = r
                    result_c = c
                elif result_r == -1 and result_c == -1:
                    result_r = r
                    result_c = c

    grounds[result_r][result_c] = cur_student
    score_help[cur_student] = cur_likes

# score 구하기
result = 0
for r in range(N):
    for c in range(N):
        cnt = 0
        for i in range(4):
            cr = r + dr[i]
            cc = c + dc[i]
            if 0 <= cr < N and 0 <= cc < N and grounds[cr][cc] in score_help[grounds[r][c]]:
                cnt += 1
        if cnt == 0:
            continue
        cnt -= 1

        result += (10 ** cnt)

print(result)

 

 

 

예전 풀이

 

# 21608 상어 초등학교

def make_seat(idx):
    cur_student = students[idx][0]
    favorite_friends = students[idx][1:]

    maximum_cnt = 0
    max_area_cnt = 0
    my_r = -1
    my_c = -1
    for r in range(1, N + 1):
        for c in range(1, N + 1):
            friend_cnt = 0
            area_cnt = 0
            if seats[r][c] == 0:
                if my_r == -1 and my_c == -1:
                    my_r = r
                    my_c = c
                # 상
                if r - 1 >= 1:
                    if seats[r - 1][c] == 0:
                        area_cnt += 1
                    if seats[r - 1][c] in favorite_friends:
                        friend_cnt += 1

                # 좌
                if c - 1 >= 1:
                    if seats[r][c - 1] == 0:
                        area_cnt += 1
                    if seats[r][c - 1] in favorite_friends:
                        friend_cnt += 1

                # 하
                if r + 1 <= N:
                    if seats[r + 1][c] == 0:
                        area_cnt += 1
                    if seats[r + 1][c] in favorite_friends:
                        friend_cnt += 1

                # 우
                if c + 1 <= N:
                    if seats[r][c + 1] == 0:
                        area_cnt += 1
                    if seats[r][c + 1] in favorite_friends:
                        friend_cnt += 1

            # 친구 수가 많으면 갱신
            if maximum_cnt < friend_cnt:
                maximum_cnt = friend_cnt
                max_area_cnt = area_cnt
                my_r = r
                my_c = c
            elif maximum_cnt == friend_cnt and max_area_cnt < area_cnt:
                max_area_cnt = area_cnt
                my_r = r
                my_c = c

    # 자리 찾아서 return
    seats[my_r][my_c] = cur_student
    return


def get_score():
    for r in range(1, N + 1):
        for c in range(1, N + 1):
            cnt = 0
            cur_list = students[seats[r][c] - 1][1:]

            # 위
            if r - 1 >= 1 and seats[r - 1][c] > 0 and seats[r - 1][c] in cur_list:
                cnt += 1

            # 좌
            if c - 1 >= 1 and seats[r][c - 1] > 0 and seats[r][c - 1] in cur_list:
                cnt += 1

            # 하
            if r + 1 <= N and seats[r + 1][c] > 0 and seats[r + 1][c] in cur_list:
                cnt += 1

            # 우
            if c + 1 <= N and seats[r][c + 1] > 0 and seats[r][c + 1] in cur_list:
                cnt += 1
            result[0] += score[cnt]

# 상 하 좌 우
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]

N = int(input())
students = [list(map(int, input().split())) for _ in range(N ** 2)]
seats = [[0] * (N + 2) for _ in range(N + 2)]
score = [0, 1, 10, 100, 1000]
result = [0]

for idx, student in enumerate(students):
    make_seat(idx)

# 학생 정렬
students.sort()
# 점수 계산
get_score()
print(result[0])


'''
4
6 5 2 3 4
5 1 9 2 8
2 9 3 1 4
4 2 5 1 7
3 1 9 4 5
9 8 1 2 3
8 1 9 3 4
7 2 3 4 8
1 9 2 5 7
10 1 2 3 4
11 1 2 3 4
12 1 2 3 4
13 1 2 3 4
14 1 2 3 4
15 1 2 3 4
16 1 2 3 4
'''