우리는 N x N 배열도 필요하므로 모든 값이 0인 배열 arr을 만들어주고, 입력값을 받아주면 됩니다.
여기서 N*N줄을 입력받을 때, 학생의 번호와 좋아하는 학생들을 딕셔너리로 저장하면 편합니다.
n = int(input())
arr = [[0]* n for _ in range(n)]
student = {}
for i in range(n*n):
x, s1, s2, s3, s4 = map(int,input().split())
student[x] = [s1, s2, s3, s4]
2. 좋아하는 학생이 가장 많이 인접한 칸
빈칸에서 좋아하는 학생이 가장 많이 인접한 칸을 찾아주면 됩니다.
우리는 좋아하는 학생이 가장 많이 인접한 칸이 여러 개일 수도 있으므로 love라는 리스트를 하나 만들어서 [인접한 좋아하는 학생 수, 좌표를 넣어줄 큐] 형태로 저장을 해야 합니다.
from collections import deque
n = int(input())
arr = [[0]* n for _ in range(n)]
student = {}
for i in range(n*n):
x, s1, s2, s3, s4 = map(int,input().split())
student[x] = [s1, s2, s3, s4]
for t in range(n*n):
love = [0, deque()]
그래서 위와 같이 collections.deque를 불러오고, 첫 번째 단계는 love라고 해서 초기값은 [ 0, deque() ]로 만들어줍니다.
그리고 이제 (0, 0)에서 (n-1, n-1)중에 빈칸만 확인해서 초깃값을 업데이트하면 됩니다.
예를 들어서 love = [ 2, deque([(0, 0), (1, 2)])] 로 되어 있으면 현재 좋아하는 사람이 가장 인접된 수는 2이고, 그 칸은 (0, 0)과 (1, 2)가 있다는 뜻입니다. 만약 (3, 4)에서 좋아하는 사람이 가장 인접된 수가 3명이 된다면 love = [ 3, deque([(3,4)])] 가 됩니다.
이번 문제에는 상하좌우가 필요하므로 dx, dy 를 만들어줍니다.
from collections import deque
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]
n = int(input())
arr = [[0]* n for _ in range(n)]
student = {}
for i in range(n*n):
x, s1, s2, s3, s4 = map(int,input().split())
student[x] = [s1, s2, s3, s4]
for t in student.keys():
love = [0, deque()]
그리고 상하좌우 인접한 자리를 확인할 때, 배열의 범위가 넘어가지 않는지 확인해야 하므로 범위 내에 있으면 True, 아니면 False를 반환하는 check 함수를 만들어주면 됩니다.
def check(x, y):
if 0 <= x < n and 0 <= y < n: return True
return False
from collections import deque
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]
n = int(input())
arr = [[0]* n for _ in range(n)]
student = {}
for i in range(n*n):
x, s1, s2, s3, s4 = map(int,input().split())
student[x] = [s1, s2, s3, s4]
for t in student.keys():
love = [0, deque()]
이제 for문을 돌려서 빈칸에서 좋아하는 사람이 가장 많이 인접한 칸을 찾으면 됩니다.
주의할 점
본문 세 번째 조건에서는 자리가 여러 개라면 1순위는 행의 번호가 가장 작은 칸을, 2순위는 열의 번호가 가장 작은 칸을 선택해야 합니다.
그래서 이건 정렬을 해야 한다고 생각할 수 있겠지만, 아래와 같이 탐색하게 되면 정렬을 하지 않아도 무조건 행의 번호가 작은 순, 행의 번호가 같으면 열의 번호가 작은 순으로 정렬될 수 있다는 것을 알 수 있습니다.
for i in range(n):
for j in range(n):
blah blah
def check(x, y):
if 0 <= x < n and 0 <= y < n: return True
return False
from collections import deque
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]
n = int(input())
arr = [[0]* n for _ in range(n)]
student = {}
for i in range(n*n):
x, s1, s2, s3, s4 = map(int,input().split())
student[x] = [s1, s2, s3, s4]
for t in student.keys():
love = [0, deque()]
for x in range(n):
for y in range(n):
if arr[x][y] == 0:
val = 0
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if check(nx, ny) and arr[nx][ny] in student[t]: val += 1
위와 같은 코드처럼 빈칸(if arr[x][y] == 0)일 때, (x, y)를 (nx, ny)로 만들어서 범위 내에 있는지 확인 후에 좋아하는 학생들 목록에 arr[nx][ny]가 들어가는지 확인해주면 됩니다. 들어가 있으면 val += 1을 해주고, 아니면 그냥 넘어가면 됩니다.
그리고 이제 val이 love[0]과 같으면 큐에 좌표를 넣어주고, val > love[0]이면 love = [ val, deque([(좌표)])]로 새로 만들어주면 됩니다.
def check(x, y):
if 0 <= x < n and 0 <= y < n: return True
return False
from collections import deque
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]
n = int(input())
arr = [[0]* n for _ in range(n)]
student = {}
for i in range(n*n):
x, s1, s2, s3, s4 = map(int,input().split())
student[x] = [s1, s2, s3, s4]
for t in student.keys():
# 좋아하는 학생이 가장 많이 인접한 칸 찾기
love = [0, deque()]
for x in range(n):
for y in range(n):
if arr[x][y] == 0:
val = 0
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if check(nx, ny) and arr[nx][ny] in student[t]: val += 1
if val == love[0]: love[1].append((x,y))
if val > love[0]: love = [val, deque([(x,y)])]
이렇게 해서 첫 번째 조건을 완료하였습니다.
이제 큐에 들어 있는 원소의 개수가 2개 이상이면 두 번째 조건으로 넘어가고, 1개이면 바로 자리를 배정하면 됩니다.
그런데 어차피 원소의 개수가 1개이면, 두 번째 조건을 돌려도 원소가 1개만 있으므로 저 값으로 결정하게 됩니다.
그래서 저는 if문 없이 그냥 코드를 추가하겠습니다.
if len(love[1]) == 1:
x, y = love[1].popleft()
arr[x][y] = student[t][0]
continue
원소의 개수가 1개일 때의 바로 자리를 배정해주는 조건문을 추가하고 싶은 분은 위 코드를 넣어주시면 됩니다.
3. 빈칸이 가장 많이 인접한 칸 찾기
이제 love[1]의 큐를 가지고 빈칸이 가장 많이 인접한 칸을 찾아주면 됩니다.
이번에는 blank라는 리스트에 값을 저장하는데, blank의 값은 [빈칸이 가장 많이 있는 개수, 좌표들을 저장할 리스트] 로 만들어주면 됩니다.
첫 번째 조건과는 다르게 큐가 아닌 리스트로 저장해주는 이유는 굳이 큐를 사용할 필요는 없기 때문입니다.
def check(x, y):
if 0 <= x < n and 0 <= y < n: return True
return False
from collections import deque
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]
n = int(input())
arr = [[0]* n for _ in range(n)]
student = {}
for i in range(n*n):
x, s1, s2, s3, s4 = map(int,input().split())
student[x] = [s1, s2, s3, s4]
for t in student.keys():
# 좋아하는 학생이 가장 많이 인접한 칸 찾기
love = [0, deque()]
for x in range(n):
for y in range(n):
if arr[x][y] == 0:
val = 0
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if check(nx, ny) and arr[nx][ny] in student[t]: val += 1
if val == love[0]: love[1].append((x,y))
if val > love[0]: love = [val, deque([(x,y)])]
# 빈칸이 가장 많은 자리 찾기
blank = [0, []]
이번엔 큐에서 원소를 빼서 확인하므로 while문을 이용하여 blank에 값을 넣어주면 됩니다.
def check(x, y):
if 0 <= x < n and 0 <= y < n: return True
return False
from collections import deque
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]
n = int(input())
arr = [[0]* n for _ in range(n)]
student = {}
for i in range(n*n):
x, s1, s2, s3, s4 = map(int,input().split())
student[x] = [s1, s2, s3, s4]
for t in student.keys():
# 좋아하는 학생이 가장 많이 인접한 칸 찾기
love = [0, deque()]
for x in range(n):
for y in range(n):
if arr[x][y] == 0:
val = 0
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if check(nx, ny) and arr[nx][ny] in student[t]: val += 1
if val == love[0]: love[1].append((x,y))
if val > love[0]: love = [val, deque([(x,y)])]
# 빈칸이 가장 많은 자리 찾기
blank = [0, []]
while love[1]:
x, y = love[1].popleft()
val = 0
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if check(nx, ny) and arr[nx][ny] == 0:
val += 1
val의 값이 blank[0]과 같으면 blank[1]에 좌표를 추가해주고, val > blank[0]이면 blank = [val, [좌표]]로 수정해주면 됩니다.
def check(x, y):
if 0 <= x < n and 0 <= y < n: return True
return False
from collections import deque
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]
n = int(input())
arr = [[0]* n for _ in range(n)]
student = {}
for i in range(n*n):
x, s1, s2, s3, s4 = map(int,input().split())
student[x] = [s1, s2, s3, s4]
for t in student.keys():
# 좋아하는 학생이 가장 많이 인접한 칸 찾기
love = [0, deque()]
for x in range(n):
for y in range(n):
if arr[x][y] == 0:
val = 0
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if check(nx, ny) and arr[nx][ny] in student[t]: val += 1
if val == love[0]: love[1].append((x,y))
if val > love[0]: love = [val, deque([(x,y)])]
# 빈칸이 가장 많은 자리 찾기
blank = [0, []]
while love[1]:
x, y = love[1].popleft()
val = 0
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if check(nx, ny) and arr[nx][ny] == 0:
val += 1
if val == blank[0]: blank[1].append((x,y))
if val > blank[0]: blank = [val, deque([(x,y)])]
이제 blank[1]에 있는 첫 번째 값은 무조건 본문 1, 2 조건을 만족하면서 행의 번호와 열의 번호가 가장 작은 좌표입니다.
그래서 blank[1]의 첫 번째 값 좌표에 t번째 학생의 번호인 student[t][0]을 저장하면 되겠습니다.
def check(x, y):
if 0 <= x < n and 0 <= y < n: return True
return False
from collections import deque
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]
n = int(input())
arr = [[0]* n for _ in range(n)]
student = {}
for i in range(n*n):
x, s1, s2, s3, s4 = map(int,input().split())
student[x] = [s1, s2, s3, s4]
for t in student.keys():
# 좋아하는 학생이 가장 많이 인접한 칸 찾기
love = [0, deque()]
for x in range(n):
for y in range(n):
if arr[x][y] == 0:
val = 0
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if check(nx, ny) and arr[nx][ny] in student[t]: val += 1
if val == love[0]: love[1].append((x,y))
if val > love[0]: love = [val, deque([(x,y)])]
# 빈칸이 가장 많은 자리 찾기
blank = [0, []]
while love[1]:
x, y = love[1].popleft()
val = 0
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if check(nx, ny) and arr[nx][ny] == 0:
val += 1
if val == blank[0]: blank[1].append((x,y))
if val > blank[0]: blank = [val, deque([(x,y)])]
# 좌석 배정
x, y = blank[0]
arr[x][y] = t
4. 점수 계산하기
이제 좌석을 다 배정했으면 점수를 더해주면 됩니다. 본문에 있는 점수 배점대로 score라는 배열을 만들어서 score = [0, 1, 10, 100, 1000]을 만들어주고, 인접하고 있는 좋아하는 학생 수대로 ans에 점수를 더해주면 됩니다.
그리고 ans를 출력하면 끝나게 됩니다.
def check(x, y):
if 0 <= x < n and 0 <= y < n: return True
return False
from collections import deque
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]
n = int(input())
arr = [[0]* n for _ in range(n)]
student = {}
for i in range(n*n):
x, s1, s2, s3, s4 = map(int,input().split())
student[x] = [s1, s2, s3, s4]
for t in student.keys():
# 좋아하는 학생이 가장 많이 인접한 칸 찾기
love = [0, deque()]
for x in range(n):
for y in range(n):
if arr[x][y] == 0:
val = 0
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if check(nx, ny) and arr[nx][ny] in student[t]: val += 1
if val == love[0]: love[1].append((x,y))
if val > love[0]: love = [val, deque([(x,y)])]
# 빈칸이 가장 많은 자리 찾기
blank = [0, []]
while love[1]:
x, y = love[1].popleft()
val = 0
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if check(nx, ny) and arr[nx][ny] == 0:
val += 1
if val == blank[0]: blank[1].append((x,y))
if val > blank[0]: blank = [val, [(x,y)]]
x, y = blank[1][0]
arr[x][y] = t
# 점수 구하기
ans = 0
score = [0, 1, 10, 100, 1000]
for x in range(n):
for y in range(n):
val = 0
for i in range(4):
nx, ny = x+dx[i],y+dy[i]
if check(nx, ny) and arr[nx][ny] in student[arr[x][y]]: val += 1
ans += score[val]
print(ans)
다른 방법
조건 1과 조건 2를 합쳐서 만들 수도 있습니다.
def check(x, y):
if 0 <= x < n and 0 <= y < n: return True
return False
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]
n = int(input())
arr = [[0]* n for _ in range(n)]
student = {}
for i in range(n*n):
x, s1, s2, s3, s4 = map(int,input().split())
student[x] = [s1, s2, s3, s4]
for t in student.keys():
# 좋아하는 학생이 가장 많이 인접한 칸이면서 빈칸이 많은 칸 찾기
best = [0, 0, []] # 좋아하는 학생 수, 빈칸의 수, 좌표
for x in range(n):
for y in range(n):
if arr[x][y] == 0:
love = 0
zero = 0
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if check(nx, ny):
if arr[nx][ny] in student[t]: love += 1
if arr[nx][ny] == 0: zero += 1
if love == best[0] and zero == best[1]: best[2].append((x,y))
if love > best[0] or (love == best[0] and zero > best[1]):
best = [love, zero, [(x,y)]]
x, y = best[2][0]
arr[x][y] = t
# 점수 구하기
ans = 0
score = [0, 1, 10, 100, 1000]
for x in range(n):
for y in range(n):
val = 0
for i in range(4):
nx, ny = x+dx[i],y+dy[i]
if check(nx, ny) and arr[nx][ny] in student[arr[x][y]]: val += 1
ans += score[val]
print(ans)
