1. 문제
21608번: 상어 초등학교
상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호
www.acmicpc.net
2. 접근
N의 범위는 3<=N<=20 이므로, 한 번 루프를 돌 때 약 최대 400번의 연산이 수행된다. 넉넉한 수행시간이므로 좌석을 하나하나 확인하여 최적의 자리를 구하기로 한다.
자리 배치에는 3개의 조건이 있고 순서대로 우선순위를 가진다
- 비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다.
- 1을 만족하는 칸이 여러 개이면, 인접한 칸 중에서 비어있는 칸이 가장 많은 칸으로 자리를 정한다.
- 2를 만족하는 칸도 여러 개인 경우에는 행의 번호가 가장 작은 칸으로, 그러한 칸도 여러 개이면 열의 번호가 가장 작은 칸으로 자리를 정한다. -> 행과 열이 더 작은 자리를 고른다.
각 조건을 만족하도록 차례대로 로직을 구현한다.
3. 로직
(1) 현재 학생과 좋아하는 학생 4명 입력받기
먼저 현재 학생과 좋아하는 학생 4명을 구한다. 모든 입력을 다 받고 확인할 필요 없고 한 줄씩 입력을 받고, 현재 학생의 자리를 배정해나간다.
students = new ArrayList[N*N+1];
// 초기화
for(int i=0; i<students.length; i++)
students[i] = new ArrayList<>();
for(int i=0; i< N*N; i++){
StringTokenizer st = new StringTokenizer(br.readLine());
int me = Integer.parseInt(st.nextToken());
// 좋아하는 학생 4명 정보 담기
for(int j=0; j<4; j++){
students[me].add(Integer.parseInt(st.nextToken()));
// .... 생략
}
(2) 인접 칸에 좋아하는 학생이 몇명인지, 비어있는 인접 칸이 몇개인지 구하기
모든 칸을 다 돌면서 하나하나 확인해준다. 인접한 칸인 상하좌우를 확인하여 4개의 칸에 좋아하는 학생이 앉아있는지 확인한다. List를 사용하여 contains()로 좋아하는 학생이 맞는지 확인한다. 이때 인접 칸의 좋아하는 학생 수의 max 값을 구하여, 후에 최적의 자리를 구하기 위해 사용한다.
비어있는 칸도 마찬가지로 모든 칸을 돌면서 확인한다. seats[i][j] 값이 초기화 값인 0이라면 비어있는 칸으로 취급한다.
seats = new int[N+1][N+1];
likeCounts =new int[N+1][N+1];
emptyCounts = new int[N+1][N+1];
// 현재 학생 좌석 배치 시작
for(int r=1; r<=N; r++){
for(int c=1; c<=N; c++){
// 이미 배정된 좌석이면 패스
if(seats[r][c] != 0)
continue;
//1. 좋아하는 학생의 수가 많은 곳
likeCounts[r][c] = getLikeCount(me, r, c);
maxLike = Math.max(maxLike, likeCounts[r][c]);
//2. 비어있는 인접 칸 몇개 인지
emptyCounts[r][c] = getEmpty(r, c);
}
}
// (r,c)에 앉을 시 인접한 칸에 좋아하는 학생이 몇명인지 리턴
public static int getLikeCount(int me, int r, int c){
int dr [] = {0, 1, 0, -1};
int dc [] = {1, 0,-1, 0};
int count = 0;
for(int i=0; i<4; i++){
int newR = r + dr[i];
int newC = c + dc[i];
if(isRange(newR,newC) && students[me].contains(seats[newR][newC]))
count++;
}
return count;
}
// (r,c)에 앉을 시 비어있는 인접한 칸이 몇개인지 리턴
public static int getEmpty(int r, int c){
int dr [] = {0, 1, 0, -1};
int dc [] = {1,0,-1,0};
int count = 0;
for(int i=0; i<4; i++){
int newR = r + dr[i];
int newC = c + dc[i];
if(isRange(newR,newC) && seats[newR][newC] == 0)
count++;
}
return count;
}
// 유효 범위인지 체크
public static boolean isRange(int r, int c){
if(r>0 && r<=N && c>0 && c<=N)
return true;
return false;
}
(3) 자리 배정
모든 칸을 돌면서 최적의 자리를 찾아준다.
조건 1. 비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다.
seats[r][c]가 0이 아니면 이미 배치된 좌석이므로 패스한다.
비어있는 좌석이라면, (2)에서 구한 가장 큰 좋아하는 학생의 수인 maxLike와 해당 칸의 likeCounts가 같은지 비교한다.
조건 2. 1을만족하는 칸이 여러 개이면, 인접한 칸 중에서 비어있는 칸이 가장 많은 칸으로 자리를 정한다.
인접 칸 중 가장 많이 비어있는 칸을 찾는다. emptyCounts에 위치에 따른 비어있는 인접 칸을 구했으므로, 해당 변수를 이용하여 갱신해나간다.
조건 3. 행과 열이 더 작은 자리를 고른다.
r과 c을 1부터 N까지 차례대로 접근하므로, maxEmpty가 같을 때 행과 열이 작은 칸을 선택한다.
int [] point = new int[2];
int maxEmpty = -1;
for(int r=1; r<=N; r++) {
for (int c = 1; c <= N; c++) {
if(seats[r][c] != 0)
continue;
// 3. 행, 열 번호가 가장 작은 곳에 배치
if(likeCounts[r][c] == maxLike){
// 인접 칸 중 가장 많이 비어있는 칸을 찾음
if(maxEmpty < emptyCounts[r][c]){
point[0] = r;
point[1] =c;
maxEmpty = emptyCounts[r][c];
}
}
}
}
seats[point[0]][point[1]] = me;
(4). 만족도 확인
결과로 인접한 칸에 좋아하는 학생 수에 따른 만족도 점수를 합쳐 출력해야 한다. 학생들의 배치 정보가 담긴 seats 배열을 순회하면서 주어진 점수표대로 점수를 부여한다.
// 4. 만족도 조사
int ans = 0;
for(int r=1; r<=N; r++) {
for (int c = 1; c <= N; c++) {
int likeCount = getLikeCount(seats[r][c], r, c);
switch (likeCount){
case 1:
ans += 1;
break;
case 2:
ans += 10;
break;
case 3:
ans += 100;
break;
case 4:
ans += 1000;
break;
}
}
}
4.전체 코드
import java.io.*;
import java.util.*;
public class Main {
static BufferedWriter bw;
static BufferedReader br;
static int N;
static int seats [][];
static int likeCounts [][];
static int emptyCounts [][];
static List<Integer>[] students;
public static void main(String[] args) throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
bw = new BufferedWriter(new OutputStreamWriter(System.out));
N = Integer.parseInt(br.readLine());
seats = new int[N+1][N+1];
likeCounts =new int[N+1][N+1];
emptyCounts = new int[N+1][N+1];
students = new ArrayList[N*N+1];
// 초기화
for(int i=0; i<students.length; i++)
students[i] = new ArrayList<>();
for(int i=0; i< N*N; i++){
int maxLike = 0;
StringTokenizer st = new StringTokenizer(br.readLine());
int me = Integer.parseInt(st.nextToken());
// 좋아하는 학생 4명 정보 담기
for(int j=0; j<4; j++){
students[me].add(Integer.parseInt(st.nextToken()));
}
// 현재 학생 좌석 배치 시작
for(int r=1; r<=N; r++){
for(int c=1; c<=N; c++){
// 이미 배정된 좌석이면 패스
if(seats[r][c] != 0)
continue;
//1. 좋아하는 학생의 수가 많은 곳
likeCounts[r][c] = getLikeCount(me, r, c);
maxLike = Math.max(maxLike, likeCounts[r][c]);
//2. 비어있는 인접 칸 몇개 인지
emptyCounts[r][c] = getEmpty(r, c);
}
}
int [] point = new int[2];
int maxEmpty = -1;
for(int r=1; r<=N; r++) {
for (int c = 1; c <= N; c++) {
if(seats[r][c] != 0)
continue;
// 3. 행, 열 번호가 가장 작은 곳에 배치
if(likeCounts[r][c] == maxLike){
// 인접 칸 중 가장 많이 비어있는 칸을 찾음
if(maxEmpty < emptyCounts[r][c]){
point[0] = r;
point[1] =c;
maxEmpty = emptyCounts[r][c];
}
}
}
}
seats[point[0]][point[1]] = me;
}
// 4. 만족도 조사
int ans = 0;
for(int r=1; r<=N; r++) {
for (int c = 1; c <= N; c++) {
int likeCount = getLikeCount(seats[r][c], r, c);
switch (likeCount){
case 1:
ans += 1;
break;
case 2:
ans += 10;
break;
case 3:
ans += 100;
break;
case 4:
ans += 1000;
break;
}
}
}
bw.write(ans+"\n");
bw.flush();
bw.close();
br.close();
}
// (r,c)에 앉을 시 비어있는 인접한 칸이 몇개인지 리턴
public static int getEmpty(int r, int c){
int dr [] = {0, 1, 0, -1};
int dc [] = {1,0,-1,0};
int count = 0;
for(int i=0; i<4; i++){
int newR = r + dr[i];
int newC = c + dc[i];
if(isRange(newR,newC) && seats[newR][newC] == 0)
count++;
}
return count;
}
// (r,c)에 앉을 시 인접한 칸에 좋아하는 학생이 몇명인지 리턴
public static int getLikeCount(int me, int r, int c){
int dr [] = {0, 1, 0, -1};
int dc [] = {1, 0,-1, 0};
int count = 0;
for(int i=0; i<4; i++){
int newR = r + dr[i];
int newC = c + dc[i];
if(isRange(newR,newC) && students[me].contains(seats[newR][newC]))
count++;
}
return count;
}
// 유효 범위인지 체크
public static boolean isRange(int r, int c){
if(r>0 && r<=N && c>0 && c<=N)
return true;
return false;
}
}728x90
'알고리즘 > 백준' 카테고리의 다른 글
| [백준] 줄 세우기 - 2252 : 위상 정렬 - JAVA (0) | 2024.02.03 |
|---|---|
| [백준] 특정 거리의 도시 찾기 - Java : 그래프 (2) | 2024.01.29 |
| [백준] 강의실 배정 : 11000 : Java - 그리디 (1) | 2024.01.22 |
| [백준] 최단 경로 : 1753 : Java - 다익스트라(Dijkstra) (0) | 2023.12.28 |
| [백준] 9934 완전 이진트리: Java - S1 (0) | 2023.12.26 |
