https://www.acmicpc.net/problem/21608
백준 21608번: 상어 초등학교 문제 풀이
이 문제는 N x N 크기의 교실에 학생들을 자리 배치하고, 친구들과의 인접도를 기준으로 만족도를 계산하는 문제입니다. 각 학생의 만족도는 인접한 친구의 수에 따라 달라지며, 자리 배치는 아래와 같은 규칙에 따라 이루어집니다.
1. 비어있는 칸 중에서 인접한 친구의 수가 가장 많은 칸 선택
2. 인접한 친구의 수가 같은 칸이 여러 개라면, 인접한 비어있는 칸이 가장 많은 칸 선택
3. 그런 칸도 여러 개라면, 행 번호가 가장 작은 칸 선택
4. 행 번호가 같은 칸이 여러 개라면, 열 번호가 가장 작은 칸 선택코드 구현
아래는 이 문제의 Java 구현 코드입니다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static class Student {
int id;
int\[\] friend;
public Student(int id, int\[\] friend) {
this.id = id;
this.friend = friend;
}
}
static int N;
static int\[\]\[\] map;
static int\[\] dx = {-1, 1, 0, 0};
static int\[\] dy = {0, 0, -1, 1};
static Student\[\] students;
public static void main(String\[\] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
students = new Student\[N \* N\];
map = new int\[N + 1\]\[N + 1\];
// 학생 정보 입력받기
for (int i = 0; i < N \* N; i++) {
st = new StringTokenizer(br.readLine());
int id = Integer.parseInt(st.nextToken());
int\[\] friend = new int\[4\];
for (int j = 0; j < 4; j++) {
friend\[j\] = Integer.parseInt(st.nextToken());
}
students\[i\] = new Student(id, friend);
}
// 자리 배치
for (Student student : students) {
assignSeat(student);
}
// 만족도 계산 및 출력
int totalSatisfaction = 0;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
for (int k = 0; k < students.length; k++) {
if (students\[k\].id == map\[i\]\[j\]) {
totalSatisfaction += calc(k, i, j); //학생 인덱스 , x y 좌표를 파라미터로 넘겨서 만족도 계산.
}
}
}
}
System.out.println(totalSatisfaction);
}
private static int calc(int studentNum, int x, int y) {
Student student = students\[studentNum\];
int score = 0;
for (int i = 0; i < 4; i++) {
int nx = x + dx\[i\];
int ny = y + dy\[i\];
if (nx < 1 || nx > N || ny < 1 || ny > N) continue;
for (int friendId : student.friend) {
if (map\[nx\]\[ny\] == friendId) {
score++;
}
}
}
// 만족도 계산
if (score == 1) return 1;
else if (score == 2) return 10;
else if (score == 3) return 100;
else if (score == 4) return 1000;
else return 0;
}
private static void assignSeat(Student student) {
int x = 0;
int y = 0;
int maxEmpty = -1;
int maxFriend = -1;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (map\[i\]\[j\] != 0) {
continue;
}
int emptyCnt = 0;
int friendCnt = 0;
for (int d = 0; d < 4; d++) {
int nx = i + dx\[d\];
int ny = j + dy\[d\];
// 범위 밖이면 무시
if (nx < 1 || nx > N || ny < 1 || ny > N)
continue;
// 친구가 인접해 있으면 친구 카운트 증가
for (int f : student.friend) {
if (f == map\[nx\]\[ny\]) friendCnt++;
}
// 비어 있는 칸 카운트 증가
if (map\[nx\]\[ny\] == 0) {
emptyCnt++;
}
}
// 조건에 따른 자리 선택
if (friendCnt > maxFriend || (friendCnt == maxFriend && emptyCnt > maxEmpty)) {
x = i;
y = j;
maxEmpty = emptyCnt;
maxFriend = friendCnt;
}
}
}
map\[x\]\[y\] = student.id;
}
} 코드 설명
1. Student 클래스
• Student 클래스는 학생의 ID와 친구들을 저장합니다.
• id: 학생의 ID
• friend: 친구들의 ID 배열
2. 자리 배치 (assignSeat 메소드)
• 각 학생이 자리에 앉을 때, 위에서 설명한 4가지 조건을 순차적으로 적용하여 최적의 자리를 찾습니다.
• 우선, 비어 있는 자리 중에서 친구가 가장 많은 자리를 선택합니다.
• 그 다음으로, 인접한 빈 자리가 많은 곳을 선택합니다.
• 마지막으로 행과 열의 번호를 기준으로 자리를 결정합니다.
3. 만족도 계산 (calc 메소드)
• 학생의 만족도는 인접한 친구의 수에 따라 1, 10, 100, 1000의 점수를 부여받습니다.
• 각 학생의 위치를 기준으로 주변에 친구가 몇 명 있는지 확인하여 점수를 계산합니다.
4. 전체 만족도 계산
• 모든 학생의 만족도를 계산하여 출력합니다.문제 해결 과정에서의 어려움
코드를 작성하면서 발생한 어려움은 Student 클래스 배열에서 학생의 ID에 접근할 때 잘못된 인덱스를 사용한 것이었습니다. 이를 해결하기 위해 학생의 ID와 인덱스 간의 관계를 명확히 파악하고 수정하였습니다.
결론
이 문제는 시뮬레이션을 기반으로 하는 문제로, 자리 배치와 만족도 계산을 위한 조건들을 잘 구현하는 것이 핵심입니다. 각 조건을 순차적으로 적용하여 문제를 해결할 수 있었습니다. 작성된 코드는 문제에서 요구하는 대로 자리 배치와 만족도 계산을 올바르게 수행합니다.