[Python] 백준 21608번 - 상어 초등학교

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

21608번: 상어 초등학교

특별한 알고리즘 없이 요구하는대로 구현만 하면 되는 문제였다.

입력값 좌표가 (1, 1) ~ (n, n) 기준이었기 때문에, 나는 (0, 0) ~ (n-1, n-1)로 수정해주었다.

또한 입력값을 list에 받으면 자리배정을 받아야 할 학생과 좋아하는 친구 list가 헷갈려서 dictionary에 담아 풀었다.

dictionary의 Key값으로는 자리 배정을 받아야하는 학생, Value 값으로는 좋아하는 학생 list를 주었다.

n = int(input())
students = [list(map(int, input().split())) for _ in range(n**2)]
dict = {}
for i in range(n**2):
    dict.update({students[i][0]-1:list(map(lambda a: a-1, students[i][1:]))})

board = [[-1]*n for _ in range(n)]

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

for stu in dict:
    seat = [(100, 100), 0, 0]     # 좌표, 친구, 빈칸
    for x in range(n):
        for y in range(n):
            # 빈칸에 대해 주변의 친구 수, 빈자리 수를 계산
            if board[x][y] == -1:
                friends = 0
                empty = 0
                for i in range(4):
                    nx = x + dx[i]
                    ny = y + dy[i]
                    if 0 <= nx < n and 0 <= ny < n:
                        if board[nx][ny] in dict[stu]:
                            friends += 1
                        elif board[nx][ny] == -1:
                            empty += 1
                
                # 1, 2, 3 조건에 의한 자리 배정
                if friends > seat[1]:
                    seat = [(x, y), friends, empty]
                elif friends == seat[1]:
                    if empty > seat[2]:
                        seat = [(x, y), friends, empty]
                    elif empty == seat[2]:
                        if nx < seat[0][0]:
                            seat = [(x, y), friends, empty]
                        elif nx == seat[0][0]:
                            if ny < seat[0][1]:
                                seat = [(x, y), friends, empty]

    board[seat[0][0]][seat[0][1]] = stu
    
# 주변의 친한 친구 수 계산
answer = 0
for x in range(n):
    for y in range(n):
        count = 0
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n and board[nx][ny] in dict[board[x][y]]:
                count += 1
        
        # 점수 계산      
        if count == 0:
            answer += 0
        elif count == 1:
            answer += 1
        elif count == 2:
            answer += 10
        elif count == 3:
            answer += 100
        elif count == 4:
            answer += 1000
            
print(answer)

처음에는 13번줄에서 seat 변수 초기값을 [(-1, -1), 0, 0]으로 주었다.

그런데 이렇게 풀면, 조건 3에서 최소 행이나 최소 열을 구할 때 최소값을 판별하지 못하게 되는 문제가 발생한다.

즉, 아래의 테스트 케이스를 통과하지 못하게 된다.

3
7 9 3 8 2 
5 7 3 8 6
3 5 2 4 9
9 6 8 3 4
8 5 3 1 6
6 3 8 5 4
2 6 4 8 7
1 8 3 4 5
4 7 9 3 8

답 자리 :
3 5 8
9 7 6
1 2 4

seat 좌표를 (-1, -1)로 주었을 때 자리 :
3 5 8
9 7 6
4 2 1

해당 케이스를 해결해주고, 2번만에 통과할 수 있었다.