문제

BOJ 21608: 상어 초등학교 https://www.acmicpc.net/problem/21608

풀이

조건

• 학생은 1번부터 N2번까지 번호가 매겨져 있고, (r, c)는 r행 c열을 의미한다. 교실의 가장 왼쪽 윗 칸은 (1, 1)이고, 가장 오른쪽 아랫 칸은 (N, N)이다.
• 한 칸에는 학생 한 명의 자리만 있을 수 있고, |r1 - r2| + |c1 - c2| = 1을 만족하는 두 칸이 (r1, c1)과 (r2, c2)를 인접하다고 한다.

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

• 학생의 만족도를 구하려면 그 학생과 인접한 칸에 앉은 좋아하는 학생의 수를 구해야 한다. 그 값이 0이면 학생의 만족도는 0, 1이면 1, 2이면 10, 3이면 100, 4이면 1000이다.

풀이 순서

• 학생 번호와 선호 친구를 저장한다.
• 저장된 학생들을 차례로 꺼내며 앉을 수 있는 자리를 찾는다.
• 탐색한 자리의 선호 점수, 주위의 빈 자리 개수, 해당 위치를 배열(able_position)에 따로 저장한다.
• (like, blank)는 내림차순으로, (좌표)는 오름차순으로 정렬해서 우선 순위가 가장 높은 위치에 해당 학생을 앉힌다.
• 모든 학생의 자리를 정한 뒤 전체 행복도를 구한다.
  • 학생들의 번호와 학생을 저장한 배열(students)의 인덱스를 일치시키기 위해 정렬한다.
• 조건에 맞춰 10의 지수로 표현된 행복도를 모두 더해 출력한다.

코드

import sys

dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]

N = int(input())

student_len = N*N
board = [[0 for _ in range(N)] for _ in range(N)]

# [학생 번호, 좋아하는 친구들] 입력
students = []
for _ in range(student_len):
    students.append(list(map(int, sys.stdin.readline().split())))

# 학생을 차례로 꺼내면서 자리 지정
for student in students:
    number = student[0] # 현재 학생 번호
    able_position = [] # 현재 학생이 앉을 수 있는 자리를 넣을 리스트
    # 교실 모든 자리를 탐색
    for i in range(N):
        for j in range(N):
            # 현재 자리가 비어있다면
            if board[i][j] == 0:
                like = 0 # 현재 자리의 선호 점수
                blank = 0 # 현재 자리 주위에 있는 빈 자리 개수
                # 4방향 탐색
                for t in range(4):
                    nx = i + dx[t]
                    ny = j + dy[t]
                    # 범위 체크
                    if nx < 0 or ny < 0 or nx >= N or ny >= N:
                        continue
                    # 탐색한 위치에 현재 학생이 선호하는 친구가 있다면
                    if board[nx][ny] in student[1:]:
                        # 선호 점수 += 1
                        like += 1
                    # 탐색한 위치가 빈 자리라면
                    if board[nx][ny] == 0:
                        # 빈 자리 개수 += 1
                        blank += 1
                # 현재 학생이 앉을 수 있는 자리 리스트에 저장
                able_position.append([like, blank, i, j])
    # 현재 학생이 앉을 수 있는 자리를 (like, blank)는 내림차순으로, (좌표)는 오름차순으로 정렬
    able_position.sort(key=lambda x:(-x[0], -x[1], x[2], [3]))
    # 조건의 우선 순위가 가장 높은 위치에 해당 학생을 앉힘
    board[able_position[0][2]][able_position[0][3]] = number

# 학생들의 행복도 조사
happy = 0 # 출력할 행복도
students.sort() # 학생들의 번호에 맞춰서 탐색하기 위해 학생 번호를 기준으로 정렬

# 모든 자리를 탐색하며 해당 자리에 앚아있는 학생을 기준으로 행복도 조사
for i in range(N):
    for j in range(N):
        like_cnt = 0 # 현재 자리에 앉아 있는 학생의 행복도
        num = board[i][j] # 현재 자리에 앉아 있는 학생의 번호
        # 현재 자리에서 4방향 탐색
        for t in range(4):
            nx = i + dx[t]
            ny = j + dy[t]
            # 범위 체크
            if nx < 0 or ny < 0 or nx >= N or ny >= N:
                continue
            # 탐색한 자리에 앉아 있는 학생이 현재 자리에 앉아 있는 학생이 선호하는 학생이라면
            if board[nx][ny] in students[num-1][1:]:
                like_cnt += 1 # 현재 자리에 앉아 있는 학생의 행복도 += 1
        # 행복도가 0이 아니라면
        if like_cnt != 0:
            # 10의 지수로 계산
            happy += (10 ** (like_cnt - 1))

print(happy)

정리

• 한 배열에 선호도, 빈자리 개수, 좌표 등을 넣고 우선순위에 맞춰 정렬하는 방법으로 쉽게 해결했다.
• 처음에는 메소드를 나눠 하려고 했는데 그러지 않는 방법이 더 간편한 것 같다.