[백준] 21608 상어 초등학교

문제

• NxN 크기의 교실에 $N^2$ 학생의 자리를 정할 때 만족도의 총 합 구하기
• 3 <= N <= 20

 

• 한 칸에는 한 명의 학생만 앉을 수 있다.
• $|r_1 - r_2| + |c_1 - c_2| = 1$ 을 만족하는 $(r_1, c_1)$과 $(r_2, c_2)를 인접하다고 한다.
• 각 학생 별로 좋아하는 학생의 번호가 주어진다.
• 학생의 만족도는 인접한 칸에 앉은 좋아하는 학생의 수에 따라 달라진다.
  • 0명 - 0점, 1명 - 1점, 2명 - 10점, 3명- 100점, 4명 - 1000점

 

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

 

풀이

• 학생들을 순서대로 앉힐 때, 고려해야할 점은 다음과 같다.
  • 1) 좋아하는 학생이 인접한 칸의 수
  • 2) 비어있는 칸의 수
  • 3) 행의 번호가 가장 작은 칸 -> 열의 번호가 가장 작은 칸
• 인접한 칸이란 각 칸의 상, 하, 좌, 우를 의미한다.
• 학생들을 순서대로 앉힌 뒤 만족도 구하기

 

• 학생들을 앉히는 순서에 대해서 고민을 많이 했는데, 그와 무관하다는 것이 포인트!

 

# 입력 받기
N = int(input())
students = [list(map(int, input().split())) for _ in range(N**2)]

# 초기 세팅
maps = [[0] * N for _ in range(N)]
dx = [-1, 1, 0, 0] 
dy = [0, 0, -1, 1]

# 학생 순서대로 앉히기
for num in range(N**2) :
    student = students[num]
    
    # 앉을 수 있는 자리 찾기
    candidates = [] 
    for i in range(N) :
        for j in range(N) :
            if maps[i][j] == 0 :
                like, blank = 0, 0
                for d in range(4) :
                    nx, ny = i+dx[d], j+dy[d]
                    if 0 <= nx < N and 0 <= ny < N :
                        if maps[nx][ny] == 0 :              # 빈 칸
                            blank += 1
                        elif maps[nx][ny] in student[1:] :  # 다른 학생이 앉음
                            like += 1
                candidates.append([like, blank, i, j])
    
    # 좋아하는 학생 수 -> 비어있는 칸 수 -> 행 번호 -> 열 번호
    candidates.sort(key=lambda x: (-x[0], -x[1], x[2], x[3]))
    maps[candidates[0][2]][candidates[0][3]] = student[0]

# 학생 만족도 구하기
answer = 0
students.sort()

for i in range(N) :
    for j in range(N) :
        score = 0
        for d in range(4) :
            nx, ny = i+dx[d], j+dy[d]
            if 0 <= nx < N and 0 <= ny < N and maps[nx][ny] in students[maps[i][j]-1] :
                score += 1
        if score != 0 :
            answer += 10 ** (score-1)

print(answer)

 

References

• 백준 구현