[백준/삼성SW역량테스트] 21608 상어 초등학교 (Python)

✏️ 문제

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

21608번: 상어 초등학교

✏️ 풀이

케이스 분류해서 차근차근 풀면 되는 문제..인데

지문 대충 읽어서 중간 중간 빠트린게 너무 많았던 문제

 

좋아하는 학생 수, 공백 수, 행/열을 차례로 비교해줘야 한다.

즉 2번 조건이 1번 조건에 종속적이기 때문에 이를 주의해야한다.

max_like이 갱신되었을 때 max_blank를 함께 갱신해준 것도 그 이유 때문..

(해당 max_like끼리 다시 2번 조건 비교할거니까)

3번 조건은 for문에서 이미 왼->오, 위->아래로 순회중이니까 딱히 비교해주지 않아도 된다. ( 2번 조건 만족하는 게 여러개여도 자동으로 무시됨 )



처음에 틀렸던 이유는,

max_x, max_y 초기값을 0, 0 으로 두고 돌렸었다.

근데 이렇게 하면 "자리 한 칸 남았는데 조건을 모두 만족하지 못하는 경우"가 있을 때 문제가 생긴다.

(친한 사람도 0이고 빈칸도 0인데 마지막 행열 비교 조건에서도 (0, 0)과 비교하니 당연히 자리를 못찾음)

 

따라서 이 경우를 해결하기 위해 초기값은 -1로 주고, 최초로 빈 자리를 만났을 때 그 값으로 할당해주었다.

✏️ 코드

import math

dx = (1, -1, 0, 0)
dy = (0, 0, -1, 1)

def check_valid(x, y):
    return 0 <= x < N and 0 <= y < N

def check_like_count(student_num):
    max_like = 0
    max_x, max_y = -1, -1

    max_blank = 0

    for i in range(N):
        for j in range(N):
            if arr[i][j] != 0: # 이미 학생 있음
                continue
            if max_x==-1 and arr[i][j] == 0:
                max_x, max_y = i, j # 최초 할당

            like = 0
            blank = 0
            for k in range(4):
                nx, ny = i + dx[k], j + dy[k]
                if check_valid(nx, ny):
                    if arr[nx][ny] in student_dict[student_num]:
                        like += 1
                    if arr[nx][ny] == 0:
                        blank += 1
            if max_like < like:
                max_like = like
                max_x, max_y = i, j
                max_blank = blank
            elif max_like == like:
                # 2번 조건
                if max_blank < blank:
                    max_blank = blank
                    max_x, max_y = i, j

    return max_x, max_y


N = int(input())
student_dict = dict()
for _ in range(N * N):
    key, *value = list(map(int, input().split()))
    student_dict[key] = value

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

for student in student_dict.keys():
    x, y = check_like_count(student)
    arr[x][y] = student

score = 0
for i in range(N):
    for j in range(N):
        like = 0
        for k in range(4):
            nx, ny = i + dx[k], j + dy[k]
            if check_valid(nx, ny):
                if arr[nx][ny] in student_dict[arr[i][j]]:
                    like += 1
        if like > 0:
            score += math.pow(10, like-1)

print(int(score))

✏️ 다른 사람 풀이

1번 조건에는 point 10점, 2번 조건에는 point 1점을 부과하여 1, 2번 조건을 한번에 비교한다.

( Point 값은 2번보다 1번이 무조건 우선이 되게끔만 잡아주면 되는 듯하다. 5점/1점도 괜찮)

참고해서 아래처럼 수정해봤다.

def check_like_count(student_num):
    max_x, max_y = -1, -1
    max_score = 0

    for i in range(N):
        for j in range(N):
            if arr[i][j] != 0: # 이미 학생 있음
                continue
            if max_x == -1 and arr[i][j] == 0:
                max_x, max_y = i, j # 최초 할당

            score = 0
            for k in range(4):
                nx, ny = i + dx[k], j + dy[k]
                if check_valid(nx, ny):
                    if arr[nx][ny] in student_dict[student_num]:
                        score += 10
                    if arr[nx][ny] == 0:
                        score += 1
            if max_score < score:
                max_score = score
                max_x, max_y = i, j

    return max_x, max_y

✏️ 생각

엣지케이스는 꼭 한 번씩 테스트 해보고 내자...! 특히 최소값 

초기값 신중하게 생각해서 넣자!