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

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

21608번: 상어 초등학교

오늘도 제가 제일 싫어하는 구현 문제를 풀었습니다. 소마 코테가 이틀남은 시점에서 구현 문제도 놓칠 수 없기에 블로그 글을 써보려고 합니다. 

 이번 문제는 글이 꽤 길어 보이지만 문제에서 조건과 사고 과정을 그대로 알려주기 때문에 설명서 보듯이 구현하면 쉽게 해결할 수 있습니다.

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

우선 첫 번째 학생의 자리는 n의 값에 관계없이 1,1로 고정이 됩니다. 그 후 2번 학생부터 빈자리를 탐색하는데 빈자리를 발견하면 dx, dy 배열로 인접한 4자리를 탐색합니다. 그리고 인접한 자리가 비었다면 zcnt를 1 증가시키고 만약 인접한 자리에 좋아하는 학생이 있다면 lcnt를 1 증가해 줍니다. 후에 빈자리 후보 배열에 자리 좌표(i, j)와 lcnt, zcnt까지 합친 튜플을 집어넣습니다. 모든 빈자리를 탐색하면 빈자리 후보 배열을 우선 zcnt 기준으로 오름차순 정렬하고 lcnt 기준으로 오름차순 정렬합니다.

 그래서 맨 앞의 원소의 좌표에 해당 학생넘버를 넣습니다. 이 과정을 첫 번째 학생을 제외한 모든 학생에 대해 반복하면 자리에 앉는 과정이 끝납니다.

 다음은 만족도를 조사하는데 똑같이 dx,dy로 인접한 자리에 좋아하는 학생이 있다면 lcnt를 1 증가시킵니다. 탐색이 끝나면 lcnt 값이 0이라면 continue 하여 패스하고, 아니라면 10의 제곱형태로 만족도를 누적합니다.

 

풀이를 굉장히 풀어서 썼기 때문에 주석은 따로 달지 않겠습니다.

import sys

 

n = int(sys.stdin.readline())

g = [list(map(int,sys.stdin.readline().split())) for _ in range(n**2)]

m = [[0 for _ in range(n)] for _ in range(n)]

m[1][1] = g[0][0]

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

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

for i in range(1,n**2):

    s = []

    like = g[i][1:]

    for j in range(n):

        for k in range(n):

            if m[j][k] != 0: continue

            lcnt = 0

            zcnt = 0

            for l in range(4):

                nx = j + dx[l]

                ny = k + dy[l]

                if 0<=nx<n and 0<=ny<n and m[nx][ny] == 0:

                    zcnt += 1

                elif 0<=nx<n and 0<=ny<n and m[nx][ny] in like:

                    lcnt += 1

            s.append((j,k,lcnt,zcnt))

    s.sort(key=lambda x: -x[3])

    s.sort(key=lambda x: -x[2])

    m[s[0][0]][s[0][1]] = g[i][0]

res = 0

for i in range(n):

    for j in range(n):

        for k in range(n**2):

            if g[k][0] == m[i][j]:

                break

        like = g[k][1:]

        lcnt = 0

        for k in range(4):

            nx = i+dx[k]

            ny = j+dy[k]

            if 0<=nx<n and 0<=ny<n and m[nx][ny] in like:

                lcnt += 1

        if lcnt ==0: continue

        res += 10**(lcnt-1)

print(res)