[백준] 21608번 / 상어초등학교 / 파이썬(Python)

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

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를 만족하는 칸도 여러 개인 경우에는 행의 번호가 가장 작은 칸으로, 그러한 칸도 여러 개이면 열의 번호가 가장 작은 칸으로 자리를 정한다.

이제 학생의 만족도를 구해야 한다. 학생의 만족도는 자리 배치가 모두 끝난 후에 구할 수 있다. 학생의 만족도를 구하려면 그 학생과 인접한 칸에 앉은 좋아하는 학생의 수를 구해야 한다. 그 값이 0이면 학생의 만족도는 0, 1이면 1, 2이면 10, 3이면 100, 4이면 1000이다.

학생의 만족도의 총 합을 구해보자.

입력

첫째 줄에 N이 주어진다. 둘째 줄부터 N2개의 줄에 학생의 번호와 그 학생이 좋아하는 학생 4명의 번호가 한 줄에 하나씩 선생님이 자리를 정할 순서대로 주어진다.

학생의 번호는 중복되지 않으며, 어떤 학생이 좋아하는 학생 4명은 모두 다른 학생으로 이루어져 있다. 입력으로 주어지는 학생의 번호, 좋아하는 학생의 번호는 N2보다 작거나 같은 자연수이다. 어떤 학생이 자기 자신을 좋아하는 경우는 없다.

출력

첫째 줄에 학생의 만족도의 총 합을 출력한다.

 

제한

• 3 ≤ N ≤ 20

 

풀이

크게 어렵지 않은 문제이다. 한명한명 학생을 앉히는데 만족도가 높게 앉히는 문제.

자리를 고르는데 몇가지 우선순위가 있다. 우선순위가 여러개이면서 단순한 경우 리스트에 담아 정렬을 이용해 단순히 구현할 수 있다. 

해야할일은 다음과 같다.

• 자리 선정
• 만족도 조사

자리선정(select)

 

우선순위가 모두 작은 경우, 큰 경우면 한번에 정렬을 통해 선택 할 수 있다.

하지만 이 문제의 경우 빈 칸이 가장 많은 경우 다음 우선순위는 좌표가 작은 순이기 때문에 두번의 정렬을 통해 해결했다.

아마 더 간단하고 쉬운 방법이 있을 것 같은데 시간이 너무 촉박해서 그냥 떠오르는 걸로 구현해버렸당

def select(student):
    candi = []
    for x in range(n):
        for y in range(n):
            blank, like = 0, 0
            # 빈칸인 경우 탐색 시작
            if classes[x][y] == 0:
                for d in range(4):
                    nx = x + dx[d]
                    ny = y + dy[d]
                    if not is_board(nx, ny):
                        continue
                    # 격자 내 존재
                    if classes[nx][ny] == 0:
                        blank += 1
                    elif classes[nx][ny] in students[student]:
                        like += 1

                candi.append([like, blank, [x, y]])
    candi.sort(reverse=True)
    # 좋아하는 학생이 인접한 칸이 많은 칸
    b_max = candi[0][0]
    l_max = candi[0][1]
    candi_2 = []
    for b, l, [x, y] in candi:
        if b < b_max :
            break
        if l < l_max:
            break
        candi_2.append([x, y])
    # 열의 번호가 가장 작은 자리
    candi_2.sort()
    if candi_2:
        return candi_2[0]
    else:
        return candi[0][2]

만족도(satis)

 

별거 아니고 그냥 만족도를 계산을 함수로 따로 뺀 것.

C언어는 swich문이 있지만 파이썬은 없으므로 그냥 if문을 반복해서 사용하면 된다.

def satis(temp):
    global result
    if temp == 1:
        result += 1
    if temp == 2:
        result += 10
    if temp == 3:
        result += 100
    if temp == 4:
        result += 1000
    return result

 

또하나의 꿀팁아닌 꿀팁...

인접한 칸 조사 할때 격자 내에 존재하는지 확인하는 부분에서 시간을 단축할 수 있다. 조건문에 조건으로 격자내에 존자하면 조사하도록 하는 것도 물론 정답이지만 시간을 좀더 절약하고 싶다면 격자 외부일때 continue를 이용하면 약간 시간이 단축 된다는 사실..! ㅎㅎ

def is_board(x, y):
    return 0 <= x < n and 0 <= y < n

조건이 참이면 True가 반환되니까 써먹도록 하쟈

 

코드

n = int(input())
arr = [list(map(int, input().split())) for _ in range(n**2)]
students = {}
for ss, s1, s2, s3, s4 in arr:
    students[ss] = [s1, s2, s3, s4]


def is_board(x, y):
    return 0 <= x < n and 0 <= y < n

classes = [[0]*n for _ in range(n)]
dx = [0, 1, -1, 0]
dy = [1, 0, 0, -1]
def select(student):
    candi = []
    for x in range(n):
        for y in range(n):
            blank, like = 0, 0
            # 빈칸인 경우 탐색 시작
            if classes[x][y] == 0:
                for d in range(4):
                    nx = x + dx[d]
                    ny = y + dy[d]
                    if not is_board(nx, ny):
                        continue
                    # 격자 내 존재
                    if classes[nx][ny] == 0:
                        blank += 1
                    elif classes[nx][ny] in students[student]:
                        like += 1

                candi.append([like, blank, [x, y]])
    candi.sort(reverse=True)
    # 좋아하는 학생이 인접한 칸이 많은 칸
    b_max = candi[0][0]
    l_max = candi[0][1]
    candi_2 = []
    for b, l, [x, y] in candi:
        if b < b_max :
            break
        if l < l_max:
            break
        candi_2.append([x, y])
    # 열의 번호가 가장 작은 자리
    candi_2.sort()
    if candi_2:
        return candi_2[0]
    else:
        return candi[0][2]
def satis(temp):
    global result
    if temp == 1:
        result += 1
    if temp == 2:
        result += 10
    if temp == 3:
        result += 100
    if temp == 4:
        result += 1000
    return result

# 자리 배치
stu = 0
result = 0

for i in range(n):
    for j in range(n):

        x, y = select(arr[stu][0])
        classes[x][y] = arr[stu][0]
        stu += 1

for x in range(n):
    for y in range(n):
        temp = 0
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]
            if 0 <= nx <n and 0<= ny < n:
                if classes[nx][ny] in students[classes[x][y]]:
                    temp += 1

        satis(temp)



print(result)