[백준] 21608 - 상어 초등학교 (Python)

문제 출처 :

www.acmicpc.net/problem/21608

21608번: 상어 초등학교

문제 풀이 :

• 삼성전자 2021년도 상반기 오전 문제중 첫번째 문제이다.
  
  삼성전자의 기출문제를 보았다면 대부분 BFS,DFS + 구현 문제로 이루어져 있는 것을 알 수 있다. 때문에 보통 필자는 삼성전자의 문제를 풀땐 어떤 부분들을 구현해야하는지 나누는걸 첫번째로 한다.
  
  요즘 추세로는 구현해야하는 것들을 문제에서 친절하게 주어주는 경우도 많다. 때문에 문제를 잘 읽어보는 것이 굉장히 중요하다.
• 문제를 읽어보면 다음을 구현하면 된다. 
  1. 입력한 순서대로 학생의 자리를 정한다.(학생의 번호 순서대로가 아니다. 입력해준 순서대로다.)
  2. 학생의 자리를 다 구했다면 학생의 만족도를 구하여 더해준다.
• 구현한 코드에 대해 살펴보자.
  
  우선 입력되는 학생은 dict형태로 받아주었다. 이렇게 받은 이유는 추후에 만족도를 조사할 때 주변 친구들 번호가 좋아하는 학생의 번호(만족도 조사를 받는 학생의) 리스트 안에 들어있는지 확인해야하는데 그런경우 key,value를 사용하는게 편해서 dict형태로 받아주었다.
  
  이후 자리를 배정하는 함수는 go 를 구현하여서 진행하였고, 만족도 조사는 2중 for문과 처음 받은 dict 형태를 통해서 진행하였다.

 

• go 함수 는 자리를 배정하는 함수이다. 입력값으로 학생의 번호를 입력 받으면 출력값은 학생의 자리를 출력해준다.
  
  함수 내부적으로는 행 , 열에 대해서 큰값 부터 작은값 순서대로 진행하며 각 map에서 dfs 방식으로 돌면서 기준에 맞게 자리를 정한다. 자리의 기준은 문제에서 주어진 1~3 을 순서대로 구현해서 진행하면 된다.
  처음에 행,열을 순회할때 큰값부터 작은값으로 간 이유는 3번 구현을 보면 만족하는 칸이 여러개인 경우 행의 번호가 작은거, 그담엔 열의 번호가 작은 거라서 큰 값부터 작은 값으로 넣고, 2번 조건만 만족해도 갱신하도록 만들어 주면 자연스럽게 3번 조건이 해결된다.

n = int(input())

students = {}
for i in range(1,(n**2)+1):
    students[i]=0

input_students = [list(map(int,input().split())) for _ in range(n**2)]

for i in input_students:
    students[i[0]] = i[1:]

dr = [1,0,0,-1]
dc = [0,-1,1,0]

maps = [[0]*n for _ in range(n)]

def go(s):
    global maps,students,dr,dc,n
    max_friends =-1
    max_empty = -1
    cur_r=-1
    cur_c =-1
    for i in range(n-1,-1,-1):
        for j in range(n-1,-1,-1):
            cur_empty=0
            cur_friends =0
            if(maps[i][j]==0):
                # print(s,i,j)
                for k in range(4):
                    nr = i + dr[k]
                    nc = j + dc[k]
                    if(nr>=n or nc>=n or nc<0 or nr<0):
                        continue
                    if(maps[nr][nc]==0):
                        cur_empty+=1
                    elif(maps[nr][nc] in students[s]):
                        cur_friends+=1
                # print(max_empty,cur_empty,max_friends,cur_friends)
                if(max_friends <= cur_friends):
                    if(max_friends ==cur_friends):
                        if(max_empty <= cur_empty):
                            cur_r = i
                            cur_c = j
                            max_friends = cur_friends
                            max_empty = cur_empty
                    else:
                        cur_r = i
                        cur_c = j
                        max_friends = cur_friends
                        max_empty = cur_empty
                # print('cur',cur_r,cur_c)
                # print()
    return  cur_r,cur_c

for i in input_students:
    s_r,s_c = go(i[0])
    maps[s_r][s_c] = i[0]

# for i in range(n):
#     for j in range(n):
#         print(maps[i][j],end='\t')
#     print()
# print()

ans =0
for i in range(n):
    for j in range(n):
        cur_num =0
        for k in range(4):
            nr = i+dr[k]
            nc = j+dc[k]
            if(nr<n and nc<n and nc>=0 and nr>=0):
                if(maps[nr][nc] in students[maps[i][j]]):
                    cur_num+=1
        if(cur_num==1):
            ans+=1
        elif(cur_num==2):
            ans+=10
        elif(cur_num==3):
            ans+=100
        elif(cur_num==4):
            ans+=1000
print(ans)