문제/백준
백준 21608 상어 초등학교 [JAVA]
javaju
2021. 12. 1. 21:54
21608번: 상어 초등학교
상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호
www.acmicpc.net
풀이 방법
학생의 자리를 정하는데 다음과 같은 규칙이 존재합니다.
- 비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다.
- 1을 만족하는 칸이 여러 개이면, 인접한 칸 중에서 비어있는 칸이 가장 많은 칸으로 자리를 정한다.
- 2를 만족하는 칸도 여러 개인 경우에는 행의 번호가 가장 작은 칸으로, 그러한 칸도 여러 개이면 열의 번호가 가장 작은 칸으로 자리를 정한다.
해당 학생이 좋아하는 학생의 번호를 저장하기 위해서 배열 안에 List를 넣어주었습니다.
해당 조건에 맞는 학생의 자리를 찾기위해 like와 empty배열을 사용하여 좋아하는 학생이 얼마나 인접해있는지와 비어있는 칸은 몇 개인지를 확인해 배열에 저장해주었습니다. 배열에 저장된 데이터를 기준으로 조건 1,2,3을 충족하는 경우에 해당 학생 자리를 배치해주는 방식으로 구현했습니다.
코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
|
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class Main_BJ_21608_상어초등학교 {
static int N, answer=0;
static int [][] seat, like, empty;
static List<Integer> list[];
static List<int []> condition1, condition2;
static int [] dx = {-1,0,1,0};
static int [] dy = {0,1,0,-1};
static int [] score = {0,1,10,100,1000};
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
seat = new int[N][N];
list = new ArrayList[N*N+1];
for(int i=1;i<N*N+1;i++) list[i] = new ArrayList<>();
for(int i=0;i<N*N;i++) {
st = new StringTokenizer(br.readLine());
int student = Integer.parseInt(st.nextToken());
for(int j=0;j<4;j++) {
list[student].add(Integer.parseInt(st.nextToken()));
}
findSeat(student);
}
cal();
System.out.println(answer);
}
public static void findSeat(int student) {
like = new int[N][N];
empty = new int[N][N];
condition1 = new ArrayList<>();
condition2 = new ArrayList<>();
for(int i=0;i<N;i++) {
for(int j=0;j<N;j++) {
if(seat[i][j]==0) {
for(int d=0;d<4;d++) {
int nx = i+dx[d];
int ny = j+dy[d];
if(range(nx,ny)) {
if(list[student].contains(seat[nx][ny])) { //인접한 좋아하는 학생
like[i][j]++;
}
else if(seat[nx][ny]==0) { //인접한 빈 곳
empty[i][j]++;
}
}
}
}
}
}
int max=0;
for(int i=0;i<N;i++) {
for(int j=0;j<N;j++) {
if(seat[i][j]==0) {
if(max<like[i][j]) {
max = like[i][j];
condition1.clear();
condition1.add(new int[] {i,j});
}else if(max==like[i][j]) {
condition1.add(new int[] {i,j});
}
}
}
}
//condition1 리스트 사이즈가 1인경우 조건1충족
if(condition1.size()==1) seat[condition1.get(0)[0]][condition1.get(0)[1]] = student;
else { //아닌 경우 조건 2,3고려
max =0;
for(int i=0;i<condition1.size();i++) {
int [] temp = condition1.get(i);
if(max<empty[temp[0]][temp[1]]) {
max = empty[temp[0]][temp[1]];
condition2.clear();
condition2.add(new int[] {temp[0],temp[1]});
}else if(max==empty[temp[0]][temp[1]]) {
condition2.add(new int[] {temp[0],temp[1]});
}
}
seat[condition2.get(0)[0]][condition2.get(0)[1]]= student;
}
}
public static boolean range(int x, int y) {
return x>=0 && x<N && y>=0 && y<N;
}
public static void cal() {
int count=0;
for(int i=0;i<N;i++) {
for(int j=0;j<N;j++) {
count=0;
for(int d=0;d<4;d++) {
int nx = i+dx[d];
int ny = j+dy[d];
if(range(nx,ny) && list[seat[i][j]].contains(seat[nx][ny])) count++;
}
answer+=score[count];
}
}
}
}
|
cs |