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

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

 

 

[문제 해석]

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

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

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

위 3가지 조건을 만족하는 자리배치를 하고, 좋아하는 학생 수에 따른 만족도 계산하여 출력하도록 한다.

---

N = int(input())

st = []
for _ in range(N**2) :
    st.append(list(map(int, input().split())))

sit = [[0]*N for n in range(N)]

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

for i in range(N**2) :
    st_num = st[i]
    tmp = []

    for r in range(N) :
        for c in range(N) :
            if sit[r][c] == 0 :
                like = 0
                blank = 0
                for k in range(4) :
                    nr, nc = r + dr[k], c + dc[k]
                    if 0 <= nr < N and 0 <= nc < N :
                        if sit[nr][nc] in st_num[1:] : 
                            like += 1
                        if sit[nr][nc] == 0 :
                            blank += 1
                tmp.append([like, blank, r, c])

    tmp.sort(key = lambda x : (-x[0], -x[1], x[2], x[3]))
    # like, blank는 클수록(-), 행과 열 수는 작을수록(+) 답
    # 인자 순서대로 오름차순으로 정렬
    sit[tmp[0][2]][tmp[0][3]] = st_num[0]
    # 정렬 후 가장 앞에 있는 리스트의 행과 열 번호에 학생 앉힘

cnt = 0
st.sort()
for p in range(N) :
    for q in range(N) :
        like = 0
        for z in range(4) :
            nr, nc = p + dr[z], q + dc[z]
            if 0 <= nr < N and 0 <= nc < N :
                if sit[nr][nc] in st[sit[p][q]-1] :
                    like += 1

        if like != 0 :
            cnt += 10 ** (like-1)

print(cnt)

---

[문제 해결]

0으로 된 3*3 배열을과 상하좌우 좌표를 미리 설정한다.

각 자리마다 상하좌우를 확인하여 좋아하는 사람이 있으면 like + 1, 빈칸이면 blank + 0를 해준다.

tmp.sort(key = lambda x : (-x[0], -x[1], x[2], x[3])) 에 따라 like, blank, 행, 열을 조건 우선순위에 따라 sort 시킨다.

like와 blank에 -를 하는 이유는 like, blank는 클수록, 행과 열은 작을수록 우선순위가 높기 때문이다.

그리고 그 우선순위에 따라 결정된 행과 열 자리에 해당 학생을 앉힌다.

모두 다 앉혔으면 만족도를 구하는데, 각 자리에 있는 학생별로 주변을 탐색해 근처에 앉아있는 좋아하는 학생수에 따라 like에 1을 더한다.

like가 0이면 0, 1이면 1, 2면 10, 3이면 100, 4면 1000이므로 이는 결국 10^(like -1)를 의미한다.

그렇기 때문에 like 값에 따라 10에 like-1 만큼을 제곱시켜 cnt 값을 구한 후 출력한다.

 

 

참고자료 : https://velog.io/@sin5015243/%EB%B0%B1%EC%A4%80-21608-%EC%83%81%EC%96%B4-%EC%B4%88%EB%93%B1%ED%95%99%EA%B5%90-Python

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