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

21608번: 상어 초등학교 (acmicpc.net)

21608번: 상어 초등학교

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

dr = [0, 1, 0, -1]
dc = [1, 0, -1, 0]

seat[1][1] = students[0][0] # 첫번째는 항상 1,1에 앉는다.

for i in range(1, N**2):
    student = students[i]
    tmp = []
    for r in range(N):
        for c in range(N):
            empty = 0
            like = 0
            if seat[r][c] == 0:
                for d in range(4):
                    nr = r + dr[d]
                    nc = c + dc[d]
                    if 0 <= nr < N and 0 <= nc < N:
                        if seat[nr][nc] == 0:
                            empty += 1
                        if seat[nr][nc] in student:
                            like += 1
                        tmp.append([like, empty, r, c])

    tmp.sort(key= lambda x:(-x[0], -x[1], x[2], x[3]))
    seat[tmp[0][2]][tmp[0][3]] = student[0]

result = 0
students.sort()
for r in range(N):
    for c in range(N):
        like = 0
        for d in range(4):
            nr = r + dr[d]
            nc = c + dc[d]
            if 0 <= nr < N and 0 <= nc < N:
                if seat[nr][nc] in students[seat[r][c]-1]:
                    like += 1
        if like <= 1:
            result += like
        elif like == 2:
            result += 10
        elif like == 3:
            result += 100
        elif like == 4:
            result += 1000

print(result)

 

BFS문제

들어갈 수 있는 모든 자리에서 조건 순서대로 계산하여 리스트에 추가하여 lambda로 정렬해주고 자리를 배치해준다.