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

문제

 

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

 

---

Algorithm

일반적인 구현 문제, 다만 요구 사항이 조금 까다로울 수 있다.
요구에 맞춰 자리를 배치 후, 만족도 총합을 구하여 하므로 크게 2파트로 나누어 생각해서 구현하였다.

 

---

 

 

Code

from collections import deque
input = __import__('sys').stdin.readline

N = int(input().rstrip())
N_list = [list(map(int, input().rstrip().split())) for i in range(N ** 2)]
N_map = [[0] * N for i in range(N)]
cntN_map = [[0] * N for i in range(N)]

def find_seat(nowNum) :
    tmpXYs = deque()
    # 1. 인접 좋아하는 학생 카운트
    for i in range(N) :
        for j in range(N) :
            tmpCnt = 0 
            if cntN_map[i][j] != -1 :
                if i > 0 :
                    if N_map[i - 1][j] in N_list[nowNum] :
                        tmpCnt += 1
                if i < N - 1 :
                    if N_map[i + 1][j] in N_list[nowNum] :
                        tmpCnt += 1
                if j > 0 :
                    if N_map[i][j - 1] in N_list[nowNum] :
                        tmpCnt += 1
                if j <  N - 1 :
                    if N_map[i][j + 1] in N_list[nowNum] :
                        tmpCnt += 1

            if tmpCnt > 0 :
                if len(tmpXYs) > 0 :
                    if tmpXYs[0][0] == tmpCnt :
                        tmpXYs.append([tmpCnt, i, j])
                    elif tmpXYs[0][0] < tmpCnt :
                        tmpXYs = [[tmpCnt, i, j]]
                else :
                    tmpXYs.append([tmpCnt, i, j])

    # 2. 비어있는 인접 칸 카운트
    if tmpXYs :
        for i in tmpXYs :
            i[0] = cntN_map[i[1]][i[2]]
    else :
        for i in range(N) :
            for j in range(N) :
                if cntN_map[i][j] != -1 :
                    tmpXYs.append([cntN_map[i][j], i, j])
    tmpXYs = list(tmpXYs)
    tmpXYs.sort(key = lambda x : (-x[0], x[1], x[2]))
    return [tmpXYs[0][1], tmpXYs[0][2]]


for i in range(N) :
    for j in range(N) :
        if (i == 0 and (j == 0 or j == N -1)) or (i == N - 1 and (j == 0 or j == N - 1)) :
            cntN_map[i][j] = 2
        elif i == 0 or i == N - 1 or j == 0 or j == N - 1 :
            cntN_map[i][j] = 3
        else :
            cntN_map[i][j] = 4
            
for i in range(N ** 2) : # 자리 배치
    seatYX = find_seat(i)
    N_map[seatYX[0]][seatYX[1]] = N_list[i][0]
    cntN_map[seatYX[0]][seatYX[1]] = -1
    if seatYX[0] > 0 and cntN_map[seatYX[0]-1][seatYX[1]] > 0:
        cntN_map[seatYX[0]-1][seatYX[1]] -= 1
    if seatYX[0] < N - 1 and cntN_map[seatYX[0]+1][seatYX[1]] > 0:
        cntN_map[seatYX[0]+1][seatYX[1]] -= 1
    if seatYX[1] > 0 and cntN_map[seatYX[0]][seatYX[1]-1] > 0:
        cntN_map[seatYX[0]][seatYX[1]-1] -= 1
    if seatYX[1] < N - 1 and cntN_map[seatYX[0]][seatYX[1]+1] > 0:
        cntN_map[seatYX[0]][seatYX[1]+1] -= 1

ans = 0
N_list.sort()
for i in range(N) : #만족도 조사
    for j in range(N) :
        tmpCnt = 0
        if i > 0 :
            if N_map[i-1][j] in N_list[N_map[i][j]-1] :
                tmpCnt += 1
        if i < N - 1 :
            if N_map[i+1][j] in N_list[N_map[i][j]-1] :
                tmpCnt += 1
        if j > 0 :
            if N_map[i][j-1] in N_list[N_map[i][j]-1] :
                tmpCnt += 1
        if j < N - 1 :
            if N_map[i][j+1] in N_list[N_map[i][j]-1] :
                tmpCnt += 1
        
        if tmpCnt == 0 :
            continue
        else :
            ans += (10 ** (tmpCnt - 1))
print(ans)

 

느낀 점

연산을 조금이라도 줄여보고자 인접한 비어있는 자리를 따로 관리하였는데, 다시 생각해보니 어차피 나중에 인접한 자리에 대해서 접근하여야 함으로 큰 차이는 없었을 것 같다는 생각이 들었다. 또한 많이 쓰이는 방향 벡터 리스트를 사용하면 코드 길이를 조금 더 줄일 수 있으나, 개인적으로 코드 읽기에 불편하여 그리하지 않았다.