21608 - 상어 초등학교

굉장히 길어보이지만 같은 코드가 중복되어있는... 코드 줄이고 싶은데 귀찮다.

주말에 문제 하나 푼게 어디냐 ^_^

 

어쨌든 구현문제라 그런지 풀이가 어려운건 아니었는데 반복문을 최소한으로 하기위해 1차원 배열에서 문제를 풀려다 보니 초기에 인덱스 설정하는데 많은 고민을 했던 문제이다.

 

그것만 아니면 크게 어려울게 없는 문제였다!

 

# 학교에 다니는 학생의 수는 N*N
# 한칸에는 한명만 앉을 수 있음 (abs(r1-r2) + abs(c1-c2) = 1)을 만족(한칸 바로 옆에 있는 경우)하는 두 칸 = 인접
# 학생의 만족도 = 인접한 칸에 앉은 좋아하는 학생의 수는 10^M (M = 인접한 칸에 앉은 좋아하는 학생의 수)
import math

N = int(input()); M = int(math.pow(N,2))

bestFriends = dict()
for i in range(M):
    tmp = list(map(int, input().split()))
    bestFriends[str(tmp[0])] = tmp[1:]

emptySpace = []
dx = [1, 0, -1, 0]; dy = [0, 1, 0 ,-1]
for i in range(N):
    for j in range(N):
        cnt = 0
        for n in range(4):
            nx = i+dx[n]; ny = j+dy[n]
            if 0<=nx<N and 0<=ny<N:
                cnt += 1
        emptySpace.append(cnt)
        
# [0[0,0], 1[0,1], 2[0,2], 3[1,0], 4[1,1], 5[1,3], 6[2,0], 7[2,1], 8[2,2]] -> [int(num//N), num-N*int(num//N)]
studentPosition = [0] * M
studentPositionArr = [[0]*N for _ in range(N)]

for key in bestFriends:
    student = key; frendList = bestFriends[key]

    # 1순위 : 빈칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸
    friendSearchList = []
    for num in range(M):
        x = int(num//N); y = num-N*int(num//N)
        cnt = 0; chk = False
        if studentPosition[num] == 0:
            chk = True
            for i in range(4):
                nx = x+dx[i]; ny = y+dy[i]
                if 0<=nx<N and 0<=ny<N and int(studentPositionArr[nx][ny]) in frendList:
                    cnt+=1

        if chk == False:
            friendSearchList.append(-1)
        else:
            friendSearchList.append(cnt)

    candiIdxList = list(filter(lambda x: friendSearchList[x] == max(friendSearchList), range(len(friendSearchList))))
    if len(candiIdxList) == 1:
        loc = friendSearchList.index(max(friendSearchList))
        x = int(loc // N);y = loc - N * int(loc // N)

        # 학생 자리 지정해주기
        studentPosition[loc] = student
        studentPositionArr[x][y] = student

        # 빈 칸 삭제
        for i in range(4):
            nx = x+dx[i]; ny = y+dy[i]
            if 0 <= nx < N and 0 <= ny < N:
                emptySpace[int(N * nx) + int(ny)] -= 1

    else:
        emptySpaceList = []
        for i in range(len(candiIdxList)):
            emptySpaceList.append(emptySpace[candiIdxList[i]])

        # 2순위 : 인접한 칸 중에서 비어있는 칸이 가장 많은 칸
        if emptySpaceList.count(max(emptySpaceList))==1:
            l = emptySpaceList.index(max(emptySpaceList))
            loc = candiIdxList[l]
            x = int(loc // N);y = loc - N * int(loc // N)

            # 학생 자리 지정해주기
            studentPosition[loc] = student
            studentPositionArr[x][y] = student

            # 빈 칸 삭제
            for i in range(4):
                nx = x + dx[i]; ny = y + dy[i]
                if 0<=nx<N and 0<=ny<N:
                    emptySpace[int(N * nx) + int(ny)] -= 1

        # 3순위 : 행의 번호가 가장 작은 칸
        # 4순위 : 열의 번호가 가장 작은 칸
        else:
            candiIdxList2 = list(filter(lambda x: emptySpaceList[x] == max(emptySpaceList), range(len(emptySpaceList))))
            rcList = []
            for i in range(len(candiIdxList2)):
                num = candiIdxList[candiIdxList2[i]]
                rcList.append([int(num//N), num-N*int(num//N)])

            rcList.sort(key = lambda x : (x[0],x[1]))

            x, y = rcList[0]
            # 학생 자리 지정해주기
            studentPosition[int(N*x) + int(y)] = student
            studentPositionArr[x][y] = student

            # 빈 칸 삭제
            for i in range(4):
                nx = x + dx[i]; ny = y + dy[i]
                if 0 <= nx < N and 0 <= ny < N:
                    emptySpace[int(N * nx) + int(ny)] -= 1

content = 0
for m in range(1, M+1):
    friendList = bestFriends[str(m)]
    loc = studentPosition.index(str(m))
    x = int(loc // N); y = loc - N * int(loc // N)
    cnt = 0
    for i in range(4):
        nx = x+dx[i]; ny = y+dy[i]
        if 0<=nx<N and 0<=ny<N and int(studentPositionArr[nx][ny]) in friendList:
            cnt+=1
    content+=int(math.pow(10, cnt-1))

print(content)