[백준, 삼성 기출] 21608_상어 초등학교 (Python)

21608_상어 초등학교 (Python)

0. 출처

• 유형 : 시뮬레이션, 삼성 (silver 1)
• 링크 : 21608번: 상어 초등학교

1. 기록

• 22/04/20 (수)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

1. 아이디어
>> 해당 index(학생번호)가 좋아하는 학생이 자리에 있는지를 찾는다.
>> 그러한 자리가 없으면 인접한 칸이 많은 빈 칸을 찾아 들어간다.
>> 그러한 자리 중 인접한 빈칸이 많은 자리로 들어가고
>> 그러한 자리 중 인접한 빈칸의 갯수 까지 같으면 행 번호, 열 번호가 작은 칸으로 들어간다.

2. 시간복잡도
>>

3. 자료구조
>> 2차원 리스트로 해결되는건지..?
>> 3차원 리스트를 써야되는건지..?

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
sample

- 예제 출력 1 -
sample

(3) 코드

import sys
from collections import defaultdict

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

n = int(input())

graph = [[0]*n for _ in range(n)]
likedict = defaultdict(list)
result = 0

for _ in range(n*n):

    # 한 줄씩 입력하고 그에 대한 자리를 잡는다.
    # 각 입력에대해 max_like 와 max_empty 를 세어본다.
    info = list(map(int, input().split()))
    likedict[info[0]] = info[1:]

    max_x = 0
    max_y = 0
    max_like = -1
    max_empty = -1

    print(f"graph 입니다. : {graph}")

    for x in range(n):
        for y in range(n):

            # 자리가 비어있는 경우
            if graph[x][y] == 0:
                likecnt = 0
                emptycnt = 0
                for i in range(4):
                    nx = x + dx[i]
                    ny = y + dy[i]
                    if 0<=nx<n and 0<=ny<n:
                        # 그 자리 주변에 호감가는 학생이 있는지 확인한다.
                        if graph[nx][ny] in info:
                            likecnt += 1

                        # 그 자리 주변에 비어있는 자리가 있는지 확인한다.
                        if graph[nx][ny] == 0:
                            emptycnt += 1

                # 좋아하는 학생이 인접한 칸에 가장 많은 칸 또는 like갯수는 max_like와 같으면서 최대 empty갯수인 경우
                # print(f"max_like 입니다. {max_like}")
                # print(f"likecnt 입니다. {likecnt}")
                # print(f"max_empty 입니다. {max_empty}")
                # print(f"emptycnt 입니다. {emptycnt}")

                # 주변의 호감학생수가 최대로 갱신되는 경우 또는 1을 만족하는 칸이 여러 칸인 경우(호감학생수는 그대로인데 빈칸 갯수가 최대로 갱신되는 경우)
                if max_like < likecnt or (max_like == likecnt and max_empty < emptycnt):
                    max_x = x
                    max_y = y
                    max_like = likecnt
                    max_empty = emptycnt

    # 그러한 곳에 자리를 잡는다.
    graph[max_x][max_y] = info[0]

for x in range(n):
    for y in range(n):
        cnt = 0
        print(f"likedict입니다 : {likedict}")
        like = likedict[graph[x][y]]

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<n and 0<=ny<n:
                # 인접한 곳에 호감학생이 있는 경우
                if graph[nx][ny] in like:
                    cnt += 1

        # cnt에 해당하는 점수를 매긴다.
        if cnt != 0:
            result += 10 ** (cnt-1)

print(result)

(4) 정리

어떻게 like수와 empty를 체크하면서 작성해야하는지 정리가 안되서 정답코드를 봤다.
defaultdict() 등 알고 있는 함수지만 써먹지 않고 있는 것들을 잘 써먹을 수 있도록 연습좀 해놔야겠다.★★

(5) 참고

참고 풀이
defaultdict() 활용법