[백준] 21608 상어 초등학교 파이썬

📌문제 링크

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

💡 문제 풀이

먼저 like 배열을 선언해서 학생 번호에 해당하는 인덱스에 좋아하는 학생의 번호 배열을 저장했다. 이래야 좋아하는 학생 수를 카운트할 때 찾기 편할 것 같아서..

ex) 학생의 번호 : 4
좋아하는 학생의 번호 : 2, 5, 1, 7
=> like[4] = [2, 5, 1, 7]

그리고 학생의 자리를 정하는 순서를 order 배열에 저장했다.
마지막으로 교실의 좌석을 표시할 seat 배열을 nXn으로 만들어줬다.

우선순위를 계산하는 알고리즘을 좀 고민했는데, 일일이 세고 조건문으로 따지기 귀찮아서 점수를 매겨주었다.

처음 만든 우선순위 계산법

좌표가 (r, c) 일 때
1. (인접한 곳의 좋아하는 학생 수) * 1000
2. (인접한 칸 중에서 비어있는 칸 수) * 100
3. (n-r) * 10
4. (n-c) * 1
1번부터 4번까지의 수를 모두 더해준다.

이런 식으로 우선순위에 따라 자리수를 다르게 하면 한 번에 점수 계산을 할 수 있을 줄 알았다....
테스트케이스랑 질문게시판의 반례 모두 통과해서 제출했는데 1초컷으로 틀렸습니다 뜸

문제를 다시 읽어보니 n의 범위가 20까지라서 생기는 문제였다!!!

(n-r) * 10 + (n-c) * 1

여기서 행 번호가 작은 게 우선이어야 하는데, n이 10일 때 (9, 10)과 (10, 0)의 점수가 같게 된다.

따라서 아래와 같이 수정했다

수정한 우선순위 계산법

좌표가 (r, c) 일 때
1. (인접한 곳의 좋아하는 학생 수) * 10
2. (인접한 칸 중에서 비어있는 칸 수) * 1
먼저 1번과 2번을 더한 점수끼리 비교한다. 
-> 코드에서는 sati 변수 사용
3. (n-r) * 100
4. (n-c) * 1
sati 값이 같을 때, 3번과 4번을 더한 점수끼리 비교한다.
-> 코드에서는 pos_sati 변수 사용

이런 식으로 계산하면 아래와 같이 출력했을 때 각 칸의 우선순위는 다음과 같다.

for i in range(n):
    for j in range(n):
        print((n - i) * 100 + (n - j), end=" ")
    print()

n = 3일 때
303 302 301
203 202 201
103 102 101

n = 10일 때
1010 1009 1008 1007 1006 1005 1004 1003 1002 1001
910 909 908 907 906 905 904 903 902 901
810 809 808 807 806 805 804 803 802 801
710 709 708 707 706 705 704 703 702 701
610 609 608 607 606 605 604 603 602 601
510 509 508 507 506 505 504 503 502 501
410 409 408 407 406 405 404 403 402 401
310 309 308 307 306 305 304 303 302 301
210 209 208 207 206 205 204 203 202 201
110 109 108 107 106 105 104 103 102 101

📋코드

중간중간 print 주석은 디버깅할 때 편하려고 만들어 둔 것이다

# 21608 상어 초등학교
n = int(input())
sn = n**2
like = [0] * (sn+1)  # i번의 학생이 좋아하는 학생 list
seat = [[0] * n for _ in range(n)]  # 교실 자리
order = [0] * sn  # 학생 순서
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

for i in range(sn):
    tmp = list(map(int, input().split()))
    order[i] = tmp[0]
    like[tmp[0]] = tmp[1:]

# 첫 번째 학생은 무조건 (1, 1) 자리 배정
# seat[1][1] = order[0]

for o in range(sn):
    num = order[o]
    # print("----------%d---------" % num)
    prior = [-1, -1]  # 가장 만족도가 높은 자리 좌표
    max_sati = 0  # 최대 만족도 갱신
    # 만족도 계산 : 좋아하는 학생 인접한 수 * 10, 비어있는 칸 수 * 1,
    # 좌표 (r, c)라면 (n-r) * 100, (n-c) * 1
    max_pos_sati = 0  # 좌표 우선순위 계산

    for i in range(n):
        for j in range(n):
            if seat[i][j] == 0:
                x = i
                y = j
                pos_sati = (n - x) * 100 + (n - y)
                sati = 0
                for k in range(4):
                    nx = x + dx[k]
                    ny = y + dy[k]
                    if 0 <= nx < n and 0 <= ny < n:
                        if seat[nx][ny] == 0:
                            sati += 1
                        elif seat[nx][ny] in like[num]:
                            sati += 10
                # print("(%d, %d) sati : %d, pos_sati : %d" % (i, j, sati, pos_sati))
                if sati > max_sati:
                    max_sati = sati
                    max_pos_sati = pos_sati
                    prior = [x, y]
                elif sati == max_sati and pos_sati > max_pos_sati:
                    # print("max_pos_sati", max_pos_sati)
                    max_pos_sati = pos_sati
                    prior = [x, y]

    # print("final", prior)
    seat[prior[0]][prior[1]] = num

# for i in range(n):
#     print(seat[i])

result = 0
for i in range(n):
    for j in range(n):
        num = seat[i][j]
        cnt = 0
        for k in range(4):
            nx = i + dx[k]
            ny = j + dy[k]
            if 0 <= nx < n and 0 <= ny < n:
                if seat[nx][ny] in like[num]:
                    cnt += 1
        if cnt > 0:
            result += 10 ** (cnt - 1)

print(result)