📝문제
https://www.acmicpc.net/problem/21608
티어: 골드5
상어 초등학교에는 교실이 하나 있고, 교실은 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를 만족하는 칸도 여러 개인 경우에는 행의 번호가 가장 작은 칸으로, 그러한 칸도 여러 개이면 열의 번호가 가장 작은 칸으로 자리를 정한다.
예를 들어, N = 3이고, 학생 N2명의 순서와 각 학생이 좋아하는 학생이 다음과 같은 경우를 생각해보자.
학생의 번호좋아하는 학생의 번호
| 4 | 2, 5, 1, 7 |
| 3 | 1, 9, 4, 5 |
| 9 | 8, 1, 2, 3 |
| 8 | 1, 9, 3, 4 |
| 7 | 2, 3, 4, 8 |
| 1 | 9, 2, 5, 7 |
| 6 | 5, 2, 3, 4 |
| 5 | 1, 9, 2, 8 |
| 2 | 9, 3, 1, 4 |
가장 먼저, 4번 학생의 자리를 정해야 한다. 현재 교실의 모든 칸은 빈 칸이다. 2번 조건에 의해 인접한 칸 중에서 비어있는 칸이 가장 많은 칸인 (2, 2)이 4번 학생의 자리가 된다.
| 4 | ||
다음 학생은 3번이다. 1번 조건을 만족하는 칸은 (1, 2), (2, 1), (2, 3), (3, 2) 이다. 이 칸은 모두 비어있는 인접한 칸이 2개이다. 따라서, 3번 조건에 의해 (1, 2)가 3번 학생의 자리가 된다.
| 3 | ||
| 4 | ||
다음은 9번 학생이다. 9번 학생이 좋아하는 학생의 번호는 8, 1, 2, 3이고, 이 중에 3은 자리에 앉아있다. 좋아하는 학생이 가장 많이 인접한 칸은 (1, 1), (1, 3)이다. 두 칸 모두 비어있는 인접한 칸이 1개이고, 행의 번호도 1이다. 따라서, 3번 조건에 의해 (1, 1)이 9번 학생의 자리가 된다.
| 9 | 3 | |
| 4 | ||
이번에 자리를 정할 학생은 8번 학생이다. (2, 1)이 8번 학생이 좋아하는 학생과 가장 많이 인접한 칸이기 때문에, 여기가 그 학생의 자리이다.
| 9 | 3 | |
| 8 | 4 | |
7번 학생의 자리를 정해보자. 1번 조건을 만족하는 칸은 (1, 3), (2, 3), (3, 1), (3, 2)로 총 4개가 있고, 비어있는 칸과 가장 많이 인접한 칸은 (2, 3), (3, 2)이다. 행의 번호가 작은 (2, 3)이 7번 학생의 자리가 된다.
| 9 | 3 | |
| 8 | 4 | 7 |
이런식으로 학생의 자리를 모두 정하면 다음과 같다.
| 9 | 3 | 2 |
| 8 | 4 | 7 |
| 5 | 6 | 1 |
이제 학생의 만족도를 구해야 한다. 학생의 만족도는 자리 배치가 모두 끝난 후에 구할 수 있다. 학생의 만족도를 구하려면 그 학생과 인접한 칸에 앉은 좋아하는 학생의 수를 구해야 한다. 그 값이 0이면 학생의 만족도는 0, 1이면 1, 2이면 10, 3이면 100, 4이면 1000이다.
학생의 만족도의 총 합을 구해보자.
💡풀이
문제 유형
구현
걸린 시간
100분
풀이 방법 도출 (주석 확인)
- 학생별 좋아하는 학생 번호 담는 인접리스트 선언
- 자리를 정할 순서대로 학생을 queue에 집어넣기 위함
- 1과 2 입력받기
- 자리 배열 선언
- 첫 번째 학생은 무조건 (1,1) by 조건에 의하여
- 입력받은 학생 순서대로 자리 배정
- 자리를 정할 학생 가져오기
- 우선순위 큐를 사용하여 주어진 조건에 맞게 정렬 설정
- 비어있는 자리를 기준으로 양옆 위아래 검사하여 비어있는 칸의 개수와 좋아하는 사람의 수 계산
- 가장 우선순위가 높은 자리를 가져와 학생 자리 배정
- 학생 만족도 구하기
//1. 좋아하는 학생이랑 가장 많이 붙을 수 있는 칸
//2. 비어있는 칸이랑 가장 많이 붙을 수 있는 칸
//3. 행의 번호가 가장 작은 칸
//4. 열의 번호가 가장 작은 칸
import java.util.*;
import java.io.*;
class Main {
static int N;
static int[][] seat;
static ArrayList<Integer>[] list;
static int[] dx = {-1, 0, 1, 0};
static int[] dy = {0, 1, 0, -1};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
StringTokenizer st;
//1)학생별 좋아하는 학생 번호 담는 인접리스트 선언
list = new ArrayList[N * N + 1];
for (int i = 0; i <= N * N; i++) {
list[i] = new ArrayList<>();
}
//2)자리를 정할 순서대로 학생을 queue에 집어넣기 위함
Queue<Integer> queue = new LinkedList<>();
//3) 1과 2 입력 받기
for (int i = 0; i < N * N; i++) {
st = new StringTokenizer(br.readLine());
int student = Integer.parseInt(st.nextToken());
int like1 = Integer.parseInt(st.nextToken());
int like2 = Integer.parseInt(st.nextToken());
int like3 = Integer.parseInt(st.nextToken());
int like4 = Integer.parseInt(st.nextToken());
queue.add(student);
list[student].add(like1);
list[student].add(like2);
list[student].add(like3);
list[student].add(like4);
}
//4) 자리 배열 선언
seat = new int[N][N];
//5) 첫번째 학생은 무조건 (1,1) by 조건에 의하여
seat[1][1] = queue.poll();
//6) 입력받은 학생 순서대로 자리 배정
while (!queue.isEmpty()) {
//7) 자리를 정할 학생 가져오기
int s = queue.poll();
//8) 우선순위 큐를 사용하여 주어진 조건에 맞게 정렬 설정
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {
//행,열,좋아하는사람,빈칸
if (a[2] != b[2]) {
return b[2] - a[2];// 좋아하는 학생이 인접한 칸에 가장 많은 칸으로
}
if (a[3] != b[3]) {
return b[3] - a[3];// 비어있는 칸이 가장 많은 칸으로
}
if (a[0] != b[0]) {
return a[0] - b[0];// 행의 번호가 가장 작은 칸으로
}
return a[1] - b[1];// 열의 번호가 가장 작은 칸으로
});
//9) 비어있는 자리를 기준으로 양옆 위아래 검사하여 비어있는 칸의 개수와 좋아하는 사람의 수 계산
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (seat[i][j] != 0) {
continue; //비어있는 칸만 검사
}
int[] result = findSeat(s, i, j);
pq.add(new int[]{i, j, result[0], result[1]});
}
}
//10) 가장 우선순위가 높은 자리를 가져와 학생 자리 배정
int[] sit = pq.poll();
seat[sit[0]][sit[1]] = s;
}
//11) 학생 만족도 구하기
int sum = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
sum += satisfied(seat[i][j], i,j);
}
}
System.out.println(sum);
}
public static int[] findSeat(int s, int x, int y) {
int likeStudent = 0;
int emptySeat = 0;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && nx < N && ny >= 0 && ny < N) {
if (list[s].contains(seat[nx][ny])) {
likeStudent++;
}
if (seat[nx][ny] == 0) {
emptySeat++;
}
}
}
return new int[]{likeStudent, emptySeat};
}
public static int satisfied(int s, int x, int y){
int likeStudent = 0;
int[] score = {0,1,10,100,1000};
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && nx < N && ny >= 0 && ny < N) {
if (list[s].contains(seat[nx][ny])) {
likeStudent++;
}
}
}
return score[likeStudent];
}
}
🤔Review
아기 상어, 청소년 상어 문제보다 10배는 수월했다 티어가 올라갈수록 확실히 문제가 복잡해지는 듯,,,
'Algorithm' 카테고리의 다른 글
| [Algorithm] 백준_컨베이어 벨트 위의 로봇_20055번 (JAVA) 🤖 (1) | 2025.04.10 |
|---|---|
| [Algorithm] 백준_마법사 상어와 비바라기_21610번 (JAVA)🪄 (1) | 2025.04.09 |
| [Algorithm] 백준_청소년 상어_19236번 (JAVA) 🐟 (0) | 2025.04.09 |
| [Algorithm] 백준_아기 상어_16236번 (JAVA) 🦈 (3) | 2025.04.08 |
| [Algorithm] 백준_특정한 최단 경로_1504번 (JAVA) 투포인터 알고리즘 (2) | 2025.04.04 |