[Baekjoon] 21608_상어 초등학교

Gold V

문제(출처: https://www.acmicpc.net/problem/21608)

---

<상어 초등학교>

문제 

 

상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호가 매겨져 있고, (r, c)는 r행 c열을 의미한다. 교실의 가장 왼쪽 윗 칸은 (1, 1)이고, 가장 오른쪽 아랫 칸은 (N, N)이다.

선생님은 학생의 순서를 정했고, 각 학생이 좋아하는 학생 4명도 모두 조사했다. 이제 다음과 같은 규칙을 이용해 정해진 순서대로 학생의 자리를 정하려고 한다. 한 칸에는 학생 한 명의 자리만 있을 수 있고, |r1 - r2| + |c1 - c2| = 1을 만족하는 두 칸이 (r1, c1)과 (r2, c2)를 인접하다고 한다.

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

* 예시는 본문 참고 (길어서 생략)

이제 학생의 만족도를 구해야 한다. 학생의 만족도는 자리 배치가 모두 끝난 후에 구할 수 있다. 학생의 만족도를 구하려면 그 학생과 인접한 칸에 앉은 좋아하는 학생의 수를 구해야 한다. 그 값이 0이면 학생의 만족도는 0, 1이면 1, 2이면 10, 3이면 100, 4이면 1000이다.

학생의 만족도의 총합을 구해보자

 

 

입력

 

첫째 줄에 N이 주어진다. 둘째 줄부터 N2개의 줄에 학생의 번호와 그 학생이 좋아하는 학생 4명의 번호가 한 줄에 하나씩 선생님이 자리를 정할 순서대로 주어진다.

학생의 번호는 중복되지 않으며, 어떤 학생이 좋아하는 학생 4명은 모두 다른 학생으로 이루어져 있다. 입력으로 주어지는 학생의 번호, 좋아하는 학생의 번호는 N2보다 작거나 같은 자연수이다. 어떤 학생이 자기 자신을 좋아하는 경우는 없다.

 

출력 

 

첫째 줄에 학생의 만족도의 총합을 출력한다.

 

 

문제 풀이

 

 - my solution (Python)

import sys

def main():
    n=int(input()) 
    arr=[[0]*n for i in range(n)]

    info=[]
    for i in range(n*n): # 정보
        info.append(list(map(int,sys.stdin.readline().split())))

    arr[1][1]=info[0][0]
    dx=[-1,1,0,0]
    dy=[0,0,-1,1]
    for i in range(1,n*n):
        temp=[[0]*n for i in range(n)]
        for j in range(n):
            for k in range(n):
                cnt=0
                zero_cnt=0
                if arr[j][k]==0:
                    for v in range(4): # 인접한 칸 중 좋아하는 학생, 비어있는 칸 구하기
                        x=j+dx[v]
                        y=k+dy[v]
                        if 0<=x<n and 0<=y<n :
                            if arr[x][y]!=0 and arr[x][y] in info[i]:
                                cnt+=1
                            elif arr[x][y]==0:
                                zero_cnt+=1

                temp[j][k]=[cnt,zero_cnt]
        num=-1
        zero_num=-1
        for j in range(n):
            for k in range(n):
                # 비어있는 칸 중 -> 좋아하는 학생이 인접한 칸에 가장 많은 칸
                if arr[j][k]==0 and temp[j][k][0]>=num:
                    if temp[j][k][0]>num:
                        xy = [j, k]
                        zero_num=temp[j][k][1]
                    else: # 만족하는 칸이 여러 개이면
                        # 인접한 칸 중에서 비어있는 칸이 가장 많은 칸
                        if temp[j][k][1]>zero_num:
                            xy = [j, k]
                            zero_num=temp[j][k][1]
                    num = temp[j][k][0]
        arr[xy[0]][xy[1]]=info[i][0]

    result=0 # 학생의 만족도
    for i in range(n):
        for j in range(n):
            for v in info:
                cnt = 0
                if arr[i][j]==v[0]:
                    for k in range(4): # 인접한 칸에 앉은 좋아하는 학생 수 구하기
                        x=i+dx[k]
                        y=j+dy[k]
                        if 0<=x<n and 0<=y<n:
                            if arr[x][y] in v:
                                cnt+=1
                    break
            if cnt==0 :
                result+=0
            elif cnt==1:
                result+=1
            elif cnt==2:
                result+=10
            elif cnt==3:
                result+=100
            else:
                result+=1000
    print(result)

if __name__=="__main__":
    main()

 

 

• n 입력
• info: N*N 줄에 학생의 번호와 학생이 좋아하는 4명의 번호 입력
• 첫 번째 학생은 인접한 칸에 좋아하는 학생의 수를 고려할 수 없으므로 빈칸이 가장 많은 칸으로 자리를 정해야 한다. 빈칸이 가장 많은 칸이 여러 개 일 수 있는 경우 이므로 행 번호가 가장 작은 칸, 열의 번호가 가장 작은 칸인 (1,1)에 첫 번째 학생 자리로 정해준다. 
• dx, dy= 인접한 칸 탐색 ( 상 하 좌 우 )
• temp = [ 좋아하는 학생의 수, 비어있는 칸의 수] 
• 전체 교실을 순환하며 인접한 칸에 있는 좋아하는 학생의 수, 비어있는 칸의 수를 세어준 후 temp에 저장해준다.
• 위에서 구한 temp를 순환하며 먼저 인접한 칸에 좋아하는 학생이 가장 많은 칸을 구해준다. 만족하는 칸이 여러 개라면 인접한 칸 중에서 비어있는 칸이 가장 많은 칸을 구해준다.
  # 여기서 3번 조건인 행의 번호가 가장 작은 칸, 열의 번호가 가장 작은 칸에 대하여 따로 조건을 걸어주지 않은 이유는 ( 0 , 0 )부터 순환하여 행의 번호가 가장 작고 열의 번호가 가장 작으며 조건에 만족하는 좌표를 찾을 수 있기 때문이다.
• result = 학생의 만족도
• 자리 배치가 모두 끝난 후 학생의 만족도를 구해준다
  = arr을 전체 순환하며 인접한 칸인 상하좌우를 탐색해준다. 인접한 칸에 좋아하는 학생이 있다면 cnt를 +1 해준다. 상하좌우 탐색 후 cnt 값에 따라 만족도인 result에 값을 더해준다.
• result 출력

 

❓ 왜 틀렸는가?

빈칸이 있지만 인접한 칸에 있는 좋아하는 학생의 수, 비어있는 칸의 수가 0인 경우를 고려하지 못했기 때문이다. 이 부분을 고려해주지 못하여 이미 자리가 정해진 곳에 다른 친구를 또 지정해줘 틀리게 된 것이었다.

 

 

---

생각🤔

 

---