[백준 21608번] 상어 초등학교 - 파이썬

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

💡문제 분석 요약

상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호가 매겨져 있고, (r, c)는 r행 c열을 의미한다. 교실의 가장 왼쪽 윗 칸은 (1, 1)이고, 가장 오른쪽 아랫 칸은 (N, N)이다.

선생님은 학생의 순서를 정했고, 각 학생이 좋아하는 학생 4명도 모두 조사했다. 이제 다음과 같은 규칙을 이용해 정해진 순서대로 학생의 자리를 정하려고 한다. 한 칸에는 학생 한 명의 자리만 있을 수 있고, |r1 - r2| + |c1 - c2| = 1을 만족하는 두 칸이 (r1, c1)과 (r2, c2)를 인접하다고 한다.

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

💡알고리즘 설계

1. 학생이 앉을 자리를 이중 배열로 설정한다.

2. 각 학생과 학생이 좋아하는 친구 리스트를 딕셔너리로 저장한다.

3. 각 학생마다, 모든 자리를 검사하며 자리가 비어있을 경우 인접한 자리를 검사한다.

4. 인접한 자리가 범위 안이면, 인접한 자리에 자신이 좋아하는 학생이 있는지, 비어있는 자리는 몇개인지 센 후 배열에 저장하고, 좋아하는 학생과 비어있는 자리의 개수가 많고 행과 열은 작은 순으로 정렬한다.

5. 정렬 후 첫번째 위치에 현재 학생을 저장한다.

6. 모든 자리를 검사한 후 주변에 좋아하는 학생이 있으면 그 학생의 수를 센 후 만족도를 더한다.

 

 

만족도를 구할 때 좋아하는 친구 리스트를 재사용해야하고, 현재 자리에 앉은 친구가 좋아하는 친구 리스트에 포함되어 있는지 확인해야하기 때문에 접근이 빠른 hash와 set을 사용했다.

처음 학생과 좋아하는 친구 리스트를 입력받을 때도 딱히 값이 변경되지 않기 때문에 list보다 tuple을 이용했다.

 

💡코드

import sys
input = sys.stdin.readline

N=int(input())
table=[[0 for _ in range(N)] for _ in range(N)]

students_hash={}
for _ in range(N*N):
    temp=tuple(map(int, input().split()))
    students_hash[temp[0]]=set(temp[1:])

dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1] #서 북 동 남

for student in students_hash:
    available=[]
    for x in range(N):
        for y in range(N):
            if table[x][y]==0:
                empty=0
                like=0
                for dir in range(4):
                    nx = x + dx[dir]
                    ny = y + dy[dir]

                    if 0<=nx<N and 0<=ny<N:
                        if table[nx][ny] in students_hash[student]:
                            like+=1
                        if table[nx][ny]==0:
                            empty+=1
                available.append((like, empty, x, y))
    available.sort(key=lambda x: (-x[0], -x[1], x[2], x[3]))
    table[available[0][2]][available[0][3]]=student

# 만족도 구하기
ans=0

for x in range(N):
    for y in range(N):
        like=0
        for dir in range(4):
            nx = x + dx[dir]
            ny = y + dy[dir]

            if 0<=nx<N and 0<=ny<N:
                if table[nx][ny] in students_hash[table[x][y]]:
                    like+=1
        if like!=0:
            ans+=10**(like-1)

print(ans)

💡시간복잡도

4중 for문이다. 그러나 입력값인 N의 최대값이 20밖에 되지 않으므로 시간은 넉넉함

(N*N)*N*N*4 => 640000

💡 느낀점 or 기억할 정보

문제와 입력값이 너무 길어서 지레 겁먹었는데 차근차근 푸니 생각보다 쉬웠다.