백준 21608 : 상어 초등학교

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

21608번: 상어 초등학교

 

해결 방법 : 브루트포스

• 입력 조건이 N <= 20 이므로, 단순하게 모든 조건을 검사하도록 구현했다. 
• 문제에 주어진 우선 순위대로 조건문을 걸기만 하면 된다.

 

import sys
input = sys.stdin.readline

def solution(N, s_dict):
    seats = [[-1 if i in [0, N+1] or j in [0, N+1] else 0 for j in range(N+2)] for i in range(N+2)]

    for s in s_dict:
        cur = [float('inf'), float('inf'), 0, 0] # row, col, num of friends, num of empty seats
        for r in range(1, N+1):
            for c in range(1, N+1):
                if seats[r][c] != 0: continue

                nextSeats = [seats[r-1][c], seats[r+1][c], seats[r][c-1], seats[r][c+1]] # 인접 자리들
                friends = len(s_dict[s] & set(nextSeats)) # 좋아하는 학생 수
                emptySeats = nextSeats.count(0) # 비어있는 좌석 수

                if friends < cur[2]: # 좋아하는 학생 수가 적으면 skip
                    continue
                elif friends == cur[2]: # 다음 우선 순위로,
                    if emptySeats < cur[3]: # 비어있는 좌석 수가 적으면 skip
                        continue
                    elif emptySeats == cur[3]: # 다음 우선 순위로
                        if r > cur[0]: # row가 더 크면 skip
                            continue
                        elif r == cur[0]: # 다음 우선 순위로,
                            if c > cur[1]: # col가 더 크면 skip
                                continue

                cur[0], cur[1], cur[2], cur[3] = r, c, friends, emptySeats # 더 괜찮은 자리 찾음
        seats[cur[0]][cur[1]] = s # 최종적으로 가장 좋은 자리로 배정

    answer = 0
    for r in range(1, N+1):
        for c in range(1, N+1):
            nextSeats = {seats[r-1][c], seats[r+1][c], seats[r][c-1], seats[r][c+1]}
            friends = len(list(nextSeats & s_dict[seats[r][c]]))
            answer += 0 if friends == 0 else 10**(friends - 1) # 만족도 합산

    return answer

if __name__ == '__main__':
    N = int(input())
    s_dict = {}
    for i in range(N**2):
        temp = list(map(int, input().strip().split()))
        s_dict[temp[0]] = set(temp[1:])
    result = solution(N, s_dict)
    print(result)