21608번: 상어 초등학교
상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호
www.acmicpc.net
문제
상어 초등학교에는 교실이 하나 있고, 교실은 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를 만족하는 칸도 여러 개인 경우에는 행의 번호가 가장 작은 칸으로, 그러한 칸도 여러 개이면 열의 번호가 가장 작은 칸으로 자리를 정한다.
학생의 만족도는 자리 배치가 모두 끝난 후에 구할 수 있다. 학생의 만족도를 구하려면 그 학생과 인접한 칸에 앉은 좋아하는 학생의 수를 구해야 한다. 그 값이 0이면 학생의 만족도는 0, 1이면 1, 2이면 10, 3이면 100, 4이면 1000이다.
학생의 만족도의 총 합을 구해보자.
입력
첫째 줄에 N이 주어진다. 둘째 줄부터 N**2개의 줄에 학생의 번호와 그 학생이 좋아하는 학생 4명의 번호가 한 줄에 하나씩 선생님이 자리를 정할 순서대로 주어진다. (단, 3 <= N <= 20)
학생의 번호는 중복되지 않으며, 어떤 학생이 좋아하는 학생 4명은 모두 다른 학생으로 이루어져 있다. 입력으로 주어지는 학생의 번호, 좋아하는 학생의 번호는 N**2보다 작거나 같은 자연수이다. 어떤 학생이 자기 자신을 좋아하는 경우는 없다.
출력
첫째 줄에 학생의 만족도의 총 합을 출력한다.
풀이 방법
이 문제는 1, 2, 3 번 문제 조건에 맞게 구현하기만 하면 되는 구현!! 이 핵심인 문제이다.
N*N 칸을 전체 탐색하며 빈 칸인 경우 인접한 칸에 좋아하는 학생이 있는지(like), 비어있는 지(empty) 확인하고 해당 카운트를 해준다. 카운트된 like, empty 수와 현재 행렬위치 i, j 는 함께 리스트에 담아 저장한다.
그 결과, 리스트에는 모든 빈 자리에 대한 like, empty 정보가 저장된다. 인접한 칸에 좋아하는 학생이 많을 수록, 비어있는 자리가 많을 수록, 행과 열 번호는 작을 수록 답이 되므로 해당 조건에 맞게 리스트를 sort 함수와 key parameter 를 함께 사용하여 정렬한다. 결과적으로 정렬된 리스트의 첫 번째 요소가 조건을 만족하는 가장 최적의 자리가 되므로 학생을 해당 자리에 배치하면 답을 얻을 수 있다!!
arr.sort(key = lambda x : (-x[0], -x[1], x[2], x[3] ))
-> 첫 번째 인자를 기준으로 먼저 정렬 후, 그 다음 두 번째, 세 번째 인자를 기준으로 순차적으로 정렬한다.
-> 오름차순이 아닌 내림차순 정렬을 원하면 값 앞에 -를 붙인다.
코드
import sys
N = int(input())
students = [list(map(int, sys.stdin.readline().split())) for _ in range(N**2)]
positions = [[0]*N for _ in range(N)] # NxN 자리 배치
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
# 순서대로 학생 자리 정하기
for student in students:
arr = []
for i in range(N):
for j in range(N):
if positions[i][j] == 0: # 빈자리면
like = 0 # 인접한 좋아하는 학생 수
empty = 0 # 인접한 비어있는 자리 수
for k in range(4):
nx, ny = i + dx[k], j + dy[k]
if 0 <= nx < N and 0 <= ny < N:
if positions[nx][ny] == 0: # 비어있는 자리면
empty += 1
elif positions[nx][ny][0] in student[1:]: # 좋아하는 학생이면 (인덱스 0에 학생 번호가 있으므로 주의)
like += 1
arr.append([like, empty, i, j])
# 좋아하는 학생 수가 많을 수록, 비어있는 자리가 많을수록, 행, 열 번호가 작을수록 답이므로 그에 맞게 정렬
arr.sort(key = lambda x : (-x[0], -x[1], x[2], [3]))
x, y = arr[0][2], arr[0][3]
positions[x][y] = student # 학생 배치
# 학생의 만족도의 총 합 구하기
satisfied = 0
for x in range(N):
for y in range(N):
student = positions[x][y]
cnt = 0
for k in range(4):
nx, ny = x + dx[k], y + dy[k]
if 0 <= nx < N and 0 <= ny < N and positions[nx][ny][0] in student[1:]:
cnt += 1
if cnt != 0:
satisfied += 10**(cnt-1)
print(satisfied)
'알고리즘 > baekjoon' 카테고리의 다른 글
| 백준 1351 무한 수열 자바(java) (0) | 2023.11.16 |
|---|---|
| 백준 17828 문자열 화폐 자바(java) (0) | 2023.11.15 |
| 백준 2661 좋은수열 자바(java) (0) | 2023.11.15 |
| 백준 19942 다이어트 자바(java) (0) | 2023.11.15 |
| 백준 1041 주사위 파이썬(Python) (1) | 2023.08.13 |