상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호가 매겨져 있고, (r, c)는 r행 c열을 의미한다. 교실의 가장 왼쪽 윗 칸은 (1, 1)이고, 가장 오른쪽 아랫 칸은 (N, N)이다.
선생님은 학생의 순서를 정했고, 각 학생이 좋아하는 학생 4명도 모두 조사했다. 이제 다음과 같은 규칙을 이용해 정해진 순서대로 학생의 자리를 정하려고 한다. 한 칸에는 학생 한 명의 자리만 있을 수 있고, |r1 - r2| + |c1 - c2| = 1을 만족하는 두 칸이 (r1, c1)과 (r2, c2)를 인접하다고 한다.
... 중간생략 ...
이제 학생의 만족도를 구해야 한다. 학생의 만족도는 자리 배치가 모두 끝난 후에 구할 수 있다. 학생의 만족도를 구하려면 그 학생과 인접한 칸에 앉은 좋아하는 학생의 수를 구해야 한다. 그 값이 0이면 학생의 만족도는 0, 1이면 1, 2이면 10, 3이면 100, 4이면 1000이다.
학생의 만족도의 총 합을 구해보자.
(https://www.acmicpc.net/problem/21608)
1, 2 조건을 만족하는 함수를 각각 만들어서 로직을 구성했다.
여기서 count라는 리스트를 만들어 인접한 곳의 정보를 저장하는데, 초기값을 -1이라고 정해야 chk 변수 결과와 겹치지 않기 때문에 유의해서 코드를 작성해야 한다.
n = int(input())
info = []
info_dic = {}
for _ in range(n**2):
a, b, c, d, e = map(int, input().split())
info.append([a, [b, c, d, e]])
info_dic[a] = [b, c, d, e]
# print(info)
board = [ list(0 for _ in range(n)) for _ in range(n)]
# print(board)
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
# 1. 좋아하는 학생이 많은 칸
def favorite(student, friend):
# student가 좋아하는 학생 리스트 - friend
# print(student, friend)
count = [ list(-1 for _ in range(n)) for _ in range(n)]
max_chk = -1
for i in range(n):
for j in range(n):
if board[i][j] == 0: #해당 칸에 자리가 있다면
chk = 0
for k in range(4):
x = i + dx[k]
y = j + dy[k]
if 0<=x<n and 0<=y<n and board[x][y] in friend: #상하좌우에 친구가 있는 수 체크
chk += 1
count[i][j] = chk
max_chk = max(chk, max_chk)
result = []
#count결과에서 친구가 가장 많은 칸 탐색
for i in range(n):
for j in range(n):
if count[i][j] == max_chk:
result.append((i, j))
return result
# 2. 인접한 칸 중에서 비어있는 칸이 많은 칸
def empty(result):
#print("result", result)
max_chk = -1
count = [ list(-1 for _ in range(n)) for _ in range(n)]
for i in range(n):
for j in range(n):
if (i, j) in result:
chk = 0
for k in range(4):
x = i + dx[k]
y = j + dy[k]
if 0<=x<n and 0<=y<n and board[x][y] == 0:
chk += 1
count[i][j] = chk
max_chk = max(chk, max_chk)
result2 = []
#count결과에서 빈 칸이 가장 많은 칸 탐색
for i in range(n):
for j in range(n):
if count[i][j] == max_chk:
result2.append((i, j))
result2.sort()
return result2
# 학생의 만족도 계산
def cal():
ans = 0
for i in range(n):
for j in range(n):
chk = 0
for k in range(4):
x = i + dx[k]
y = j + dy[k]
if 0<=x<n and 0<=y<n and board[i][j] != 0:
if board[x][y] in info_dic[board[i][j]]:
chk += 1
if chk > 0:
ans += 10**(chk-1)
return ans
for inf in info:
rlt1 = favorite(inf[0], inf[1:][0])
if len(rlt1) > 1:
rlt2 = empty(rlt1)
mx, my = rlt2[0][0], rlt2[0][1]
else:
mx, my = rlt1[0][0], rlt1[0][1]
board[mx][my] = inf[0]
print(cal())
1, 2 조건에 따라 함수를 만들다 보면 겹치는 부분이 보인다. 한번에 인접한 곳에 좋아하는 친구가 있는지, 빈칸이 있는지 계산할 수 있다.
n = int(input())
member = {}
for _ in range(n**2):
a, b, c, d, e = map(int, input().split())
member[a] = [b, c, d, e]
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
arr = [list(0 for _ in range(n)) for _ in range(n)]
def main(a):
max_count_friend = -1
max_count_empty = -1
fit_i, fit_j = 0, 0
for i in range(n):
for j in range(n):
if arr[i][j] == 0:
count_friend = 0
count_empty = 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 member[a]:
count_friend += 1
if arr[x][y] == 0:
count_empty += 1
#1. 좋아하는 친구가 인접한 칸에 가장 많은 칸인경우
if count_friend > max_count_friend:
fit_i = i
fit_j = j
# 수정부분 : max friend의 count가 기준이 되어야 다른 칸에서 빈 칸이 제일 많은 곳 판단가능
max_count_friend = count_friend
max_count_empty = count_empty
#2. 1을 만족하는 칸이 여러개인 경우
if count_friend == max_count_friend:
if count_empty > max_count_empty:
fit_i = i
fit_j = j
# 수정부분
#max_count_friend = count_friend
max_count_empty = count_empty
arr[fit_i][fit_j] = a
for key in member.keys():
main(key)
# print(key)
# for a in arr:
# print(a)
# print("")
answer = 0
for i in range(n):
for j in range(n):
cnt = 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 member[arr[i][j]]:
cnt += 1
if cnt >= 1:
answer += 10**(cnt-1)
print(answer)