문제

21608번: 상어 초등학교

접근

• 다음 케이스를 잘 분류해야 한다. 이 케이스를 계산하고 정렬 과정 역시 필요하다.

1. 비어있는 칸 중 좋아하는 학생이 인접 자리에 많은 곳에 위치 지정
2. 1번 조건 해당 케이스가 여러 개면 인접 칸 중 빈자리 개수가 가장 많은 곳에 위치 지정
3. 2번 조건 해당 케이스가 여러 개면 행 번호가 최소인 자리 → 열 번호 최소인 자리

• 형태가 복잡한 중첩 리스트와, 딕셔너리를 잘 활용해야 한다.
• 탐색은 BFS를 푸는 것과 유사하게 접근하면 된다.
• 탐색하는 인덱스 위치가 자리선정이 된 곳인지 True, False로 따로 판별하려 했지만, 그것보단 3*3 배열 자체가 0으로 셋팅됐다가 0이 아닌 값으로 채워지면 자리선정이 된 것이므로 이를 활용하는게 더 간단했다.

내 코드

# BOJ 21608번: 상어 초등학교
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

n = int(input())
n_square = n ** 2
students = [list(map(int, input().split())) for _ in range(n_square)]

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

for s in range(n_square):
    tmp = []
    for i in range(n):
        for j in range(n):
            sumLike, sumEmpty = 0, 0
            if arr[i][j] != 0:
                continue
            for k in range(4):
                nx = i + dx[k]
                ny = j + dy[k]
                if nx < 0 or nx > n-1 or ny < 0 or ny > n-1:
                    continue
                if arr[nx][ny] in students[s][1:]:
                    sumLike += 1
                if arr[nx][ny] == 0:
                    sumEmpty += 1
            tmp.append((sumLike, sumEmpty, (i, j)))
    tmp.sort(key=lambda x: (-x[0], -x[1], x[2]))

    arr[tmp[0][2][0]][tmp[0][2][1]] = students[s][0]

# print(arr)
# print(students)

likes = {}
for i in range(n_square):
    tmp = students[i][0]
    likes[tmp] = students[i][1:]

# print(likes)
result = 0
for i in range(n):
    for j in range(n):
        cnt = 0
        for k in range(4):
            nx = i + dx[k]
            ny = j + dy[k]
            if nx < 0 or nx > n - 1 or ny < 0 or ny > n - 1:
                continue
            if arr[nx][ny] in likes[arr[i][j]]:
                cnt += 1
                continue
        if cnt != 0:
            result += 10 ** (cnt - 1)

print(result)

if arr[nx][ny] in students[s][1:]:과 같이 in으로 포함 여부를 편리하게 추출할 수 있으므로 이를 잘 활용하는 연습을 해봐야 할 것 같다. 덧붙여 likes[tmp] = students[i][1:]와 같이 리스트 슬라이싱을 하는 것도 굉장히 편리했다. 또한 key를 기준으로 정렬하는 부분이 굉장히 편리하다.

// 최근 SK 1차 코딩테스트 당일 부터 파이썬을 사용하기 시작했는데, 문법만 익숙해지면 자바를 사용하는 것 보다 훨씬 편하게 풀이할 것 같다.