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

 

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

 

21608번: 상어 초등학교

1. 이 문제는 처음 읽고 든 생각은 일단 딕셔너리를 사용하긴 하는데.. 조건을 어떻게 구현하지? 였습니다.
2. 그래서 그냥 조건을 한 줄 한 줄 읽어보면서 차례대로 구현했습니다.
3. 먼저 주어진 학생의 번호와 그 학생이 좋아하는 학생의 번호를 딕셔너리로 만들어서 저장해놓았습니다.
4. 주어진 조건 세개를 한 번 다시 보겠습니다.
   1. 비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다.
   2. 1을 만족하는 칸이 여러 개이면, 인접한 칸 중에서 비어있는 칸이 가장 많은 칸으로 자리를 정한다.
   3. 2를 만족하는 칸도 여러 개인 경우에는 행의 번호가 가장 작은 칸으로, 그러한 칸도 여러 개이면 열의 번호가 가장 작은 칸으로 자리를 정한다.
5. 좋아하는 학생이 많은 칸으로 가려면 좋아하는 학생의 수가 담긴 변수가 필요할 거고, 두 번째 순서로 비어있는 칸이 가장 많은 칸으로 자리를 정하려면 비어있는 칸의 수가 담긴 변수 또한 필요할 것입니다. 그리고 공통적으로 칸의 정보가 담길 x, y 좌표도 필요하기 때문에 temp라는 리스트를 만들어서 위의 정보 4개를 넣어줬습니다.
   
   
6. 다음으로 가장 중요한, 각 순서를 만족하면 다음 순서를 넘어가는 조건을 구현하기 위해 정렬을 사용했습니다.
7. 마지막으로 만족도를 구해주기 위해 2중 for문을 이용해서 result값을 구해줬습니다.

import sys
from collections import defaultdict 
input = sys.stdin.readline

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

n = int(input())
dict = defaultdict(list)

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
graph = [[0 for _ in range(n)] for _ in range(n)]

for _ in range(n*n):
    a = list(map(int,input().rstrip().split()))
    student = a[0]
    like = a[1:]
    dict[student] = like
    
# 모든 학생들 탐색
for student, like in dict.items():
    tmp= []
    #각 학생들에 대해서 board를 탐색하면서 자리 정보 tmp에 저장
    for i in range(n):
        for j in range(n):
            empty = 0
            cnt=0
            if graph[i][j] != 0:
                continue
            for k in range(4):
                nx, ny = i+ dx[k], j+dy[k]
                if nx<0 or nx>=n or ny<0 or ny>=n:
                    continue
                if graph[nx][ny] == 0:
                    empty += 1
                if graph[nx][ny] in like:
                    cnt += 1
            tmp.append([cnt, empty, i, j])
    # 자리정보 정렬
    print('---------------------------------')
    print(tmp)
    tmp.sort(key = lambda x: (-x[0],-x[1], x[2],x[3]))
    # 가장 앞에 있는 자리가 베스트.
    print(tmp)
    graph[tmp[0][2]][tmp[0][3]] = student
    # print('---------------------------------')
    # for i in range(n):
    #     for j in range(n):
    #         print(graph[i][j],end=" ")
    #     print()
    # print('---------------------------------')
result = 0
for i in range(n):
    for j in range(n):
        amount = 0
        for k in range(4):
            nx, ny = i+ dx[k], j+dy[k]
            if nx<0 or nx>=n or ny<0 or ny>=n:
                continue
            if graph[nx][ny] in dict[graph[i][j]]:
                amount += 1
        # print(amount)
        if amount == 0:
            result += 0
        elif amount == 1:
            result += 1
        else:
            result += 10 ** (amount-1)
print(result)

 

 

개발자 친구 왈, 

 

'조건을 그냥 ide에 주석으로 옮겨놓고 하나하나 처리한다는 생각으로 구현해라'