21608 - 상어 초등학교

 

---

 

문제

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

21608번: 상어 초등학교

 

풀이

 

우선 입력값을 1차원 배열에 저장하고, 학생번호로도 접근할 수 있도록 딕셔너리에도 세팅해둔다.

 

그 다음은 2차원 배열을 모두 돌면서 어느자리가 적합한지를 판단해야한다.

 

선호하는 친구의 수, 빈칸의 공간을 매 칸마다 확인하며, 이전에 저장한 최댓값보다 크다면 갱신해주고 아니라면 넘어가면 되는 식으로 구현하면 된다.

 

단, 귀찮은 부분이 있는데 친구도, 빈칸도 같을때이다. 이 때는 가장작은 행, 가장작은 열을 선택해야 한다.

이 경우를 쉽게 넘기기 위해서 n*n 부터 1, 1 로 루프를 돌도록 만들었다. 조건(친구랑 빈칸수)이 같을땐 결국 좌상단으로 향해야 한다는 말이기 때문에 값을 바로 갱신해주는 방식으로 구현했다.

 

코드

from sys import stdin

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

n = int(input())

friends = []

classRoom = [[0] * n for _ in range(n)]
posistion = {}
for i in range(n*n):
    s, f1, f2, f3, f4 = map(int, stdin.readline().rstrip().split())
    friends.append([s, f1, f2, f3, f4])
    posistion[s] = i

for friend in friends:

    fx = fy = 0
    numOfFriend = 0
    empty = 0
    for x in range(n-1, -1, -1):
        for y in range(n-1, -1, -1):

            if classRoom[x][y] != 0:
                continue

            t_numOfFriend = 0
            t_empty = 0
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]

                if 0<=nx<n and 0<=ny<n:
                    if classRoom[nx][ny] in friend:
                        t_numOfFriend += 1
                    elif classRoom[nx][ny] == 0:
                        t_empty += 1

            # 갱신 작업
            if t_numOfFriend > numOfFriend:
                numOfFriend = t_numOfFriend
                empty = t_empty
                fx = x
                fy = y


            elif t_numOfFriend == numOfFriend:
                if t_empty > empty:
                    empty = t_empty
                    fx = x
                    fy = y
                elif t_empty == empty:
                    fx = x
                    fy = y
    classRoom[fx][fy] = friend[0]

answer = 0

for x in range(n):
    for y in range(n):
        val = classRoom[x][y]
        cnt = 0
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<n and 0<=ny<n:
                if classRoom[nx][ny] in friends[posistion[val]]:
                    cnt += 1

        if cnt == 1: answer += 1
        if cnt == 2: answer += 10
        if cnt == 3: answer += 100
        if cnt == 4: answer += 1000

print(answer)

 

후기

 

무난무난 문제다. 단 갱신해주거나 분기주는 부분을 놓치기 쉬워 조금은 주의해야한다. 나도 빈공간까지 같을때 처리를 안했어서 중간에 한 번 틀렸다.