[백준] 상어 초등학교

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

21608번: 상어 초등학교

구현 문제입니다. 

 

우선 문제부터 간단하게 요약하면, 

학생들을

비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다. 1을 만족하는 칸이 여러 개이면, 인접한 칸 중에서 비어있는 칸이 가장 많은 칸으로 자리를 정한다. 2를 만족하는 칸도 여러 개인 경우에는 행의 번호가 가장 작은 칸으로, 그러한 칸도 여러 개이면 열의 번호가 가장 작은 칸으로 자리를 정한다.

다음의 규칙에 알맞게 배열해야 하는 것입니다. 그리고 이 학생들의 만족도를 구하는 것이 문제입니다. (실제로 문제가 조금 길어서 한번 읽어보는 것을 추천합니다.)

 

<Solution>

특별한 알고리즘이 쓰이지는 않는 구현 문제입니다.

 

하지만 매번 학생들을 놓을 때 마다 상하좌우를 확인하는 것 보단 미리미리 저장하는 것이 좋을 것 같다고 생각하여서, 필요한 것들을 미리미리 저장하면서 가도록 하였습니다.

seat_nearby = [[set() for _ in range(N)] for _ in range(N)] # each seat memorize students nearby
seat = [[0] * N for _ in range(N)]
seat_nearby_empty = [[4]*N for _ in range(N)]

위와 같이 seat_nearby는 특정 자리의 상하 좌우에 어떤 학생들이 들어있는지를 기억하도록 하였고, 

seat는 그냥 말 그대로 현재 그 자리에 앉아 있는 학생을 저장, 

마지막으로 seat_nearby_empty는 이웃한 것들중 빈 자리가 몇개가 있는지를 저장해 두게 하였습니다. 

 

실제 구현은 아래와 같습니다. (각각의 step을 함수화 시켜서 return 시키는 방향이 더 편할 듯 합니다.)

import sys
from collections import defaultdict
N = int(sys.stdin.readline().rstrip())

dir_r = [0, 0, -1, 1] # right left up down
dir_c = [1, -1, 0, 0]

def oob(N, r, c):
    return r<0 or c<0 or r>N-1 or c>N-1

seat_nearby = [[set() for _ in range(N)] for _ in range(N)] # each seat memorize students nearby
seat = [[0] * N for _ in range(N)]
seat_nearby_empty = [[4]*N for _ in range(N)]

for i in range(N):
    seat_nearby_empty[0][i] -= 1
    seat_nearby_empty[i][0] -= 1
    seat_nearby_empty[i][N-1] -= 1
    seat_nearby_empty[N-1][i] -= 1

line_dict = defaultdict(list)

for i in range(N**2):

    end_flag = False
    line = list(map(int, sys.stdin.readline().rstrip().split()))
    student = line[0]
    like = line[1:]
    line_dict[student] = like
    # step 1
    candidate = [[],[],[],[],[]]
    num = int(2e9)
    for r in range(N):
        for c in range(N):
            if seat[r][c] == 0:
                k = 0
                for e in like:
                    if e in seat_nearby[r][c]:
                        k += 1
                candidate[k].append((r,c))
    
    for e in candidate[::-1]:
        if len(e) != 0:
            if len(e) == 1:
                r, c = e[0]
                seat[r][c] = student
                # update nearby
                for j in range(4):
                    new_r = r + dir_r[j]
                    new_c = c + dir_c[j]
                    if not oob(N, new_r,new_c):
                        seat_nearby[new_r][new_c].add(student)
                        seat_nearby_empty[new_r][new_c] -= 1

                end_flag = True
                break
            else:
                break # go to step 2

    if end_flag:
        continue
    # step 1 end

    # step 2
    step3_flag = False
    t = [[],[],[],[],[]]
    for e in candidate[::-1]:
        if len(e) == 0:
            continue
        for k in e:
            t[seat_nearby_empty[k[0]][k[1]]].append((k[0],k[1]))
        for t_ in t[::-1]:
            if len(t_) != 0:
                if len(t_) == 1:
                    r, c = t_[0]
                    seat[r][c] = student
                    # update nearby
                    for j in range(4):
                        new_r = r + dir_r[j]
                        new_c = c + dir_c[j]
                        if not oob(N, new_r,new_c):
                            seat_nearby[new_r][new_c].add(student)
                            seat_nearby_empty[new_r][new_c] -= 1
                    end_flag = True
                    break
                else : 
                    step3_memorize = t_
                    step3_flag = True
                    break # go to step 3
            if end_flag or step3_flag:
                break
        if end_flag or step3_flag:
            break
    
    if end_flag:
        continue

    # step 3
    r, c = step3_memorize[0]
    seat[r][c] = student
    # update nearby
    for j in range(4):
        new_r = r + dir_r[j]
        new_c = c + dir_c[j]
        if not oob(N, new_r,new_c):
            seat_nearby[new_r][new_c].add(student)
            seat_nearby_empty[new_r][new_c] -= 1

# print(seat)
total_satisfaction = 0
for r in range(N):
    for c in range(N):
        student = seat[r][c]
        like = line_dict[student]
        count = 0
        for j in range(4):
            new_r = r + dir_r[j]
            new_c = c + dir_c[j]
            if not oob(N, new_r,new_c) and seat[new_r][new_c] in like:
                count+=1

        if count == 0:
            total_satisfaction += 0
        elif count == 1:
            total_satisfaction += 1
        elif count == 2:
            total_satisfaction += 10
        elif count == 3:
            total_satisfaction += 100
        elif count == 4:
            total_satisfaction += 1000
        
print(total_satisfaction)