[알고리즘] 상어 초등학교 - 구현

문제

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

21608번: 상어 초등학교

 

풀이 팁

( 다른 풀이 블로그를 보면 하나의 함수에서 다들 list에 담아서 (x,y,like_cnt, empty_cnt)를 정렬하여 반환하는데 실제 코테에서는 그 생각을 못할거 같다 )

 

1. 조건이 3가지가 있는데 2가지(1,2번)를 한번에 처리해준다. 

- how_many_friends_i_like 함수 참조

- 가독성 좋게 작성했으니 한눈에 이해하기 쉬울것이다.

 

2. arr안에서 현재 번호의 학생, 좋아하는 친구들을 받아서 작성하는데, like수와 empty수가 모두 같을때 처리하는 부분에서 오래걸렸다 

- like 수가 max보다 많을때 empty 수를 변환시키기

- 1,2번 조건이 모두 같을때 cur_x, cur_y 가 모두 -1이라면 cur_x,cur_y를 모두 x,y로 바꿔주기

 

이건 내가 적었던 질문인데 혹시 코드를 보고 이해가 안간다면 참고용으로 보셔도됩니다.

https://www.acmicpc.net/board/view/138407

글 읽기 - 왜 틀린지 모르겠습니다 ㅠ 피드백이나 반례 부탁드리고 싶습니다!!

 

코드

import sys

n = int(input())

dxs, dys = [-1,0,0,1], [0,-1,1,0]

# 학생번호, 좋아하는 친구 4명
arr = [
    list(map(int,input().split()))
    for _ in range(n*n)
]

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

ans = 0
score = {
    0 : 0,
    1 : 1,
    2 : 10,
    3 : 100,
    4 : 1000
}

def in_range(x,y):
    return 0<=x<n and 0<=y<n

# 북 서 동 남 순서로 ( 행-열 순서 맞춤 )
def how_many_friends_i_like(x,y,friends):
    like_cnt, empty_cnt = 0, 0
    for dx,dy in zip(dxs,dys):
        nx,ny = x + dx, y + dy

        if not in_range(nx,ny):
            continue

        if temp[nx][ny] in friends:
            like_cnt += 1
        
        if temp[nx][ny] == 0:
            empty_cnt += 1
    
    return like_cnt, empty_cnt



for i in arr:
    cur_num, f1,f2,f3,f4 = i

    tmp = [f1,f2,f3,f4]

    max_like_cnt, max_empty_cnt, cur_x, cur_y = 0,0,-1,-1
    
    for x in range(n):
        for y in range(n):
            if temp[x][y] != 0:
                continue

            like_cnt, empty_cnt = how_many_friends_i_like(x,y,tmp)
            
            if max_like_cnt < like_cnt:
                max_like_cnt = like_cnt
                max_empty_cnt = empty_cnt
                cur_x,cur_y = x,y
                

            elif max_like_cnt == like_cnt:
                
                if max_empty_cnt < empty_cnt:
                    
                    max_empty_cnt = empty_cnt
                    cur_x,cur_y = x,y
                
                elif max_empty_cnt == empty_cnt:
                    if cur_x == -1 and cur_y == -1:
                        cur_x,cur_y = x,y
                    elif cur_x > x:
                        cur_x,cur_y = x,y
                    elif cur_x == x and cur_y > y:
                        cur_x,cur_y = x,y


            
    
    temp[cur_x][cur_y] = cur_num

for x in range(n):
    for y in range(n):
        for i in arr:
            cur_num, f1,f2,f3,f4 = i

            tmp = [f1,f2,f3,f4]

            cnt = 0

            if temp[x][y] == cur_num:

                for dx,dy in zip(dxs, dys):
                    nx,ny = x + dx, y + dy

                    if not in_range(nx,ny):
                        continue

                    if temp[nx][ny] in tmp:
                        cnt += 1
            
            ans += score[cnt]
print(ans)