21608: 상어 초등학교

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

21608번: 상어 초등학교

설명

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

상어 초등학교의 교실은 N x N 격자이다. 학교에 다니는 학생의 수는 N^2 명이다. 1 <= 학생 수 <= N^2. 학생마다 번호가 매겨져 있다. 두 학생이 인접하다는 뜻은 |r1 - r2| + |c1 - c2| = 1 을 만족하는 것이다. 

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

결국, 1. 내 주변에 좋아하는 사람이 가장 많은 칸 2. 비어있는 칸이 가장 많은 칸 3. 행의 번호가 낮은 칸 4. 열의 번호가 낮은 칸

 

핵심 아이디어

• 문제에 나온 대로 구현하면 된다.
• students 배열을 돌면서 각 학생이 앉을 수 있는 자리를 모두 구해 정렬한 뒤, 학생의 자리를 정한다.
  • 먼저 모든 자리를 돌면서 빈자리가 있는지 확인
  • 빈자리가 있다면, 그 자리에서 거리가 1인 방향을 모두 확인하여 주위에 학생이 좋아하는 학생이 있는지 확인 후, prefer변수에 더해 준다.
  • 그리고 주위에 빈자리가 있다면 empty 변수에 더해준다.
  • 주위 네 방향을 모두 확인한 후, (행, 열, 좋아하는 학생의 수, 빈자리의 수)를 배열에 담아준다.
  • 빈자리 모두 확인하고 나서 정렬한 뒤, 제일 먼저 오는 자리에 학생을 넣어준다.
• 모든 자리에 학생이 있다면 점수를 계산한다.
  • 주위 돌면서 좋아하는 학생의 수를 세서 ans에 더해 준다.

코드 구현

n = int(input())
# 정보를 담을 리스트 만들기
data = [[0] * n for _ in range(n)]
students = []
for _ in range(n**2):
	# 학생의 번호, 좋아하는 학생의 번호
	students.append(list(map(int, input().split())))
# 상 하 좌 우 방향
dx = [-1,1,0,0]
dy = [0,0,-1,1]
for student in students:
	available = [] # 해당 학생의 (행,열,좋아하는 학생의 수, 빈칸 수) 저장할 배열
	for i in range(n):
		for j in range(n):
			# 빈자리가 있다면
			if data[i][j] == 0:
				prefer, empty = 0,0 # 먼저, 초기화 0
				# 4가지 방향 확인
				for k in range(4):
					nx = i + dx[k]
					ny = j + dy[k]
					# 범위내에 있다면
					if (0 <= nx < n) and (0 <= ny < n):
						# 좋아하는 학생이 주위에 있다면 더해준다.
						if data[nx][ny] in student[1:]:
							prefer += 1
						# 빈자리가 있다면 더해준다.
						if data[nx][ny] == 0:
							empty += 1
				# available 배열에 (행, 열, 좋아하는 사람 수, 빈칸 수)
			    # 를 모두 더 해준다.
				available.append((i,j,prefer,empty))
	# 정렬해준다.
	# 1. 좋아하는 사람 많은 수 2. 빈칸 많은 수 3. 행의 번호가 낮은 순
	# 4. 열의 번호가 낮은 순
	# -붙으면 내림차순, +이면 오름차순
	available.sort(key = lambda x: (-x[2], -x[3], x[0], x[1]))
	# 학생을 배치한다.
	data[available[0][0]][available[0][1]] = student[0]

# 최종 결과 변수 -> 학생 만족도 합
ans = 0
# 각 만족도
score = [0, 1, 10, 100, 1000]
students.sort() # 학생을 정렬해서 순서대로 만족도를 계산한다.
# 만족도 계산은 위에서 자리 배치가 모두 끝난 후 진행 한다. 이제 만족도 계산하기
for i in range(n):
	for j in range(n):
		count = 0 # 주변에 좋아하는 학생의 수
		for k in range(4):
			nx = i + dx[k]
			ny = j + dy[k]
			if (0 <= nx < n) and (0 <= ny < n):
				# 인접칸에 좋아하는 학생이 있다면
                # students[data[i][j] - 1]는 현재 검사하는 학생이 좋아하는 사람 리스트
                # -1을 해주는 이유는 학생 번호와 인덱스 차이때문 학생 번호는 1부터 시작
                # 인덱스는 0부터 시작!
				if data[nx][ny] in students[data[i][j] - 1][1:]: # 좋아하는 사람이 있다면
					count += 1 # 주변에 좋아하는 학생 수에 따라 더한다.
		ans += score[count]
print(ans)