문제
상어 초등학교에는 교실이 하나 있고, 교실은 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를 만족하는 칸도 여러 개인 경우에는 행의 번호가 가장 작은 칸으로, 그러한 칸도 여러 개이면 열의 번호가 가장 작은 칸으로 자리를 정한다.
정답코드
# 상어 초등학교
# 복습 횟수:2, 01:00:00, 복습필요X
import sys
si = sys.stdin.readline
N = int(si())
student_list = []
student_dict = dict()
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
for i in range(N*N):
student = list(map(int, si().split()))
student_list.append(student)
student_dict[student[0]] = student[1:]
graph = [[0 for _ in range(N)] for __ in range(N)]
# 탐색 시직
for student in student_list:
# 1. 비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다.
target = student[0]
like_student = set(student[1:]) # 시간복잡도를 줄이기 위해 해시 사용
like_list = []
for x in range(N):
for y in range(N):
if graph[x][y] != 0: continue
cnt = 0
for idx in range(4):
nx, ny = x + dx[idx], y + dy[idx]
if not (0 <= nx < N and 0 <= ny <N): continue
if graph[nx][ny] in like_student:
cnt += 1
like_list.append([x, y, cnt])
max_like_index = [] # 가장 max 찾기
maxi = 0
for i in range(len(like_list)):
maxi = max(maxi, like_list[i][2])
for i in range(len(like_list)):
if like_list[i][2] == maxi:
max_like_index.append([like_list[i][0], like_list[i][1], like_list[i][2]])
if len(max_like_index) == 1:
x = max_like_index[0][0]
y = max_like_index[0][1]
graph[x][y] = target
continue
else: # 1을 만족하는 칸이 여러 개이면, 인접한 칸 중에서 비어있는 칸이 가장 많은 칸으로 자리를 정한다.
empty_list = []
for i in range(len(max_like_index)):
x = max_like_index[i][0]
y = max_like_index[i][1]
cnt = 0
for idx in range(4):
nx, ny = x + dx[idx], y + dy[idx]
if not( 0 <= nx < N and 0 <= ny < N): continue
if graph[nx][ny] == 0: #비어있다면
cnt += 1
empty_list.append([x, y, cnt])
maxi = 0
for i in range(len(empty_list)):
maxi = max(maxi, empty_list[i][2])
tmp = []
for i in range(len(empty_list)):
if empty_list[i][2] == maxi:
tmp.append([empty_list[i][0], empty_list[i][1]])
if len(tmp) == 1:
graph[tmp[0][0]][tmp[0][1]] = target
else: # 2를 만족하는 칸도 여러 개인 경우에는 행의 번호가 가장 작은 칸으로, 그러한 칸도 여러 개이면 열의 번호가 가장 작은 칸으로 자리를 정한다.
tmp.sort(key=lambda x: (x[0], x[1]))
graph[tmp[0][0]][tmp[0][1]] = target
# 만족도의 총합 구하기
answer = 0
for x in range(N):
for y in range(N):
target = graph[x][y]
value = student_dict[target]
cnt = 0
for idx in range(4):
nx, ny = x + dx[idx], y + dy[idx]
if not (0 <= nx < N and 0 <= ny < N):continue
if graph[nx][ny] in value:
cnt += 1
if cnt == 0:
answer += 0
elif cnt == 1:
answer += 1
elif cnt == 2:
answer += 10
elif cnt == 3:
answer += 100
else:
answer += 1000
print(answer)
풀이
1. 그냥 빡구현 문제이다. 그래서 딱히 풀이는 없고 그냥 구현 스타일로 디버깅하면서 문제를 해결하였다.
'Koala - 9기 > 코딩테스트 준비 스터디' 카테고리의 다른 글
[BOJ/Python] 1981 배열에서 이동 (0) | 2023.02.10 |
---|---|
[백준 / Python] 7117번 Sevens, twos and zeros (0) | 2023.02.07 |
[BOJ/Python] 2075 N번째 큰 수 (0) | 2023.02.06 |
[백준/C++] 3190번 뱀 (0) | 2023.02.05 |
[백준/Python] 2178번 미로 탐색 (0) | 2023.02.05 |