[python] BOJ 백준 21608: 상어 초등학교

1. 문제  

상어 초등학교에는 교실이 하나 있고, 교실은 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이다.

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

2. 입력   

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

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

3. 출력   

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

4. 해결방법   

이 문제는 구현, 시뮬레이션 문제이다. 반복문과 조건문이 많고, 코드가 좀 길어지는 문제이다. 하지만 문제에서 하라는대로 차례대로 함수를 작성해주면된다. 먼저 인접한 개수를 저장하는 가중치 배열(board)이 필요한데, 문제에서 2번째 조건으로 비어있는 칸이 가장 많은 칸으로 자리를 정하라고 하였기 때문이다. 또한 이미 자리가 정해진 부분을 체크하는 배열(flag)도 필요하기 때문에 먼저 True값으로 초기화해주었다. 또한 학생번호에 대해서 어떤 자리에 앉아있는지도 저장하는 딕셔너리(seat)를 생성해주었다. 인접개수 가중치배열은 인접한 칸이 많을수록 숫자가 작게 설정해주었다. 그 이유는 나중에 비어있는칸-행의번호가 작은칸-열의번호가 작은칸 순으로 정렬을 하게 되는데 오름차순으로 한번에 정렬하는것이 편하기 때문이다. 좋아하는 학생 4명을 딕셔너리에 저장해주었다면 이제 이 번호들을 순서대로 돌면서 자리를 탐색해주면된다.

만약 좋아하는 학생이 이미 앉았다면, 그 상하좌우 옆자리가 앉을수 있는 후보군이 될것이다. 이때 좋아하는 학생이 많이 앉아있어서 그 옆자리가 겹쳤다면 최대한 많이 겹친자리에 앉아야 하므로, 일단 배열에 넣어놓고 카운터 함수를 사용하여 제일 많이 겹치는 자리들만을 후보군으로 등록해주었다. 만약 좋아하는 학생이 앉지 않았다면, 빈자리가 후보군이 될것이다. 

후보군들이 여러개라면 비어있는칸-행의번호가 작은칸-열의번호가 작은칸 순으로 정렬을 해준다음 제일 첫번째 것이 최종 자리가 된다. 최종자리로 등록할때는 seat 배열, flag배열 뿐만아니라 가중치배열 board도 업데이트가 필요하다. 인접한 칸 4개에 대해서 가중치가 증가하기 때문이다. 자리를 모두 지정해주었다면, 좋아하는 학생번호들을 탐색하면서 거리가 1인 학생들이 몇명이냐에 따라서 만족도를 증가시켜주면된다. 

5) 구현코드   

from collections import Counter
n=int(input())
dic={} #좋아하는 학생 
board=[[2]*n for _ in range(n)] #인접개수 가중치배열 
flag=[[True]*n for _ in range(n)] #정해진 자리 
seat={} #정해진 자리 좌표

#상하좌우 
dx=[0,0,1,-1]
dy=[1,-1,0,0]

#인접한 칸이 많을수록 숫자는 작게 가중치 설정 
for i in range(n):
  for j in range(n):
    if i==0 or j==0 or i==n-1 or j==n-1:
      board[i][j]=3 
board[0][0],board[0][n-1],board[n-1][0],board[n-1][n-1]=4,4,4,4

#좋아하는 학생 4명 입력받기 
for _ in range(n**2):
  a,b,c,d,e=map(int,input().split())
  dic[a]=[b,c,d,e] 

#자리 정하기 
for key in dic.keys():
  candidate=[] #앉을수있는 자리 후보군 
  #좋아하는 학생 번호를 돌면서 
  for value in dic[key]:
    #좋아하는 학생이 이미 앉았다면 
    if value in seat.keys():
      for i in range(4): #그 자리의 상하좌우 자리가 
        nx,ny=seat[value][0]+dx[i],seat[value][1]+dy[i]
        #범위안에있고 아무도 앉았다면 후보군 등록 
        if 0<=nx<n and 0<=ny<n and flag[nx][ny]:
          candidate.append((nx,ny,board[nx][ny]))

  if candidate: #후보군이 있을경우 
    set_candidate=list(set(candidate))
    #후보군들 중에 좋아하는 학생여러명이 앉아있을 경우 
    if set_candidate!=candidate:
      #개수를 세주고 
      c=Counter(candidate).most_common()
      candidate=[]
      max_num=c[0][1] #좋아하는 학생이 겹치는 최대값
      for a,b in c:
        if b==max_num: #후보군 자리등록 
          candidate.append(a)

  else: #후보군이 없을경우
    for i in range(n):
      for j in range(n):
        if flag[i][j]: #아직 안앉은 자리는 모두 후보군 
          candidate.append((i,j,board[i][j]))

  #후보군이 여러개일경우 인접한칸 중 비어있는 칸이 많은 순 
  candidate.sort(key=lambda x:(x[2],x[0],x[1]))
  x,y=candidate[0][0],candidate[0][1] #최종 후보 
  seat[key]=[x,y] #자리 정해주기 
  flag[x][y]=False #자리 앉은여부 체크 
  #상하좌우 인접한 칸 가중치 증가 
  for i in range(4):
      nx,ny=x+dx[i],y+dy[i]
      if 0<=nx<n and 0<=ny<n and flag[nx][ny]:
        board[nx][ny]+=1

answer=0 #최종만족도 
for key in dic.keys():
  x,y=seat[key]
  cnt=0 
  for value in dic[key]:
    nx,ny=seat[value][0],seat[value][1]
    if 0<=abs(nx-x)+abs(ny-y)<=1:
      cnt+=1
  if cnt==1:
    answer+=1
  if cnt==2:
    answer+=10
  if cnt==3:
    answer+=100
  if cnt==4:
    answer+=1000

print(answer)

 

⭐️난이도:  실버 1 ⭐️

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

21608번: 상어 초등학교