[백준Java]BOJ21608_상어초등학교
<출처 : https://www.acmicpc.net/problem/21608>
문제 설명은 길어서 패스...
나의 풀이 생각
- 배열을 오른쪽 아래에서 왼쪽 위로 쭉 돌면서 좋아하는 친구가 더 많은 자리가 있으면 바꾸고, 좋아하는 친구의 수가 같을 때 비어있는 자리가 더 많으면 바꾸고, 비어있는 자리마저 같으면 행이 적은 칸, 행 마저 같으면 열이 적은 칸으로 위치를 지정하면 된다고 생각했다.- 문제 풀면서 헷갈리고 애를 먹었던 점은 지나온 자리의 정보와 현재 자리의 정보를 비교할 때 헷갈렸는데.. 현재 자리에서 좋아하는 학생의 수가 더 많으면 지나온 자리의 비어있는 자리를 현재 자리의 비어있는 자리의 값으로 바꿨어야 했는데 그걸 나중에 알아서 좀 고생했다.(우선순위가 비어있는 자리보다 좋아하는 학생의 수가 더 많기 때문)
코드
좀 더 짧고 간결하게 풀어보고 싶었는데 다른 분들의 풀이도 비슷한 것 같다...
import java.util.Scanner;
public class BOJ21608_상어초등학교 {
static int[][] arr; // 배열
static int[][] favorite; // 좋아하는 학생
static int[] order;
static int[] dy = { 1, 0, -1, 0 };
static int[] dx = { 0, -1, 0, 1 };
static int n;
static Scanner sc;
static class FavorEmptyInfo {
int favoriteCnt = 0;
int emptyCnt = 0;
}
public static void main(String[] args) throws Exception {
sc = new Scanner(System.in);
n = sc.nextInt();
order = new int[n*n];
arr = new int[n][n];
favorite = new int[n * n + 1][4];
getFavoriteStudents();
int pickY = -1;
int pickX = -1;
FavorEmptyInfo tmp;
FavorEmptyInfo pickInfo;
for(int pickIdx=0;pickIdx<n*n;pickIdx++) { // 1~n*n까지의 학생 순서
pickInfo = new FavorEmptyInfo(); //현재 순번의 학생의 주변에 (좋아하는 학생, 비어있는 자리) 정보
tmp = new FavorEmptyInfo();
pickY = -1;
pickX = -1;
for (int i = n - 1; i >= 0; i--) {
for (int j = n - 1; j >= 0; j--) {
if(arr[i][j]!=0)continue;
tmp = searchFavorite(i,j, order[pickIdx]); //현재 위치에서 좋아하는 학생, 비어있는 자리 정보
if(pickInfo.favoriteCnt<tmp.favoriteCnt) { //주변에 좋아하는 학생의 수가 더 많으면
pickInfo.favoriteCnt = tmp.favoriteCnt;
pickInfo.emptyCnt = tmp.emptyCnt;
pickY = i;
pickX = j;
continue;
}
else if(pickInfo.favoriteCnt==tmp.favoriteCnt) { //주변에 좋아하는 학생의 수가 같으면
if(pickInfo.emptyCnt<tmp.emptyCnt) { //주변에 비어있는 자리가 더 많으면
pickInfo.emptyCnt = tmp.emptyCnt;
pickY = i;
pickX = j;
}
else if(pickInfo.emptyCnt == tmp.emptyCnt) {
pickY=i;
pickX=j;
}
}
}
}
arr[pickY][pickX] = order[pickIdx];
}
System.out.println(calcArr());
}
public static void getFavoriteStudents() { // 좋아하는 학생 입력받기
int student = 0;
for (int i = 0; i < n * n; i++) {
student = sc.nextInt();
order[i] = student;
for (int j = 0; j < 4; j++) {
favorite[student][j] = sc.nextInt();
}
}
}
public static FavorEmptyInfo searchFavorite(int y, int x, int pickIdx) {
FavorEmptyInfo cnt = new FavorEmptyInfo();
int ny = 0;
int nx = 0;
for (int dir = 0; dir < 4; dir++) {
ny = y + dy[dir];
nx = x + dx[dir];
if (ny >= n || ny < 0 || nx >= n || nx < 0)
continue; // 범위를 나갈때
if (arr[ny][nx] == 0) {
cnt.emptyCnt++;
continue;
}
for (int i = 0; i < 4; i++) {
if (favorite[pickIdx][i] == arr[ny][nx]) {
cnt.favoriteCnt++;
break;
}
}
}
return cnt;
}
public static int calcArr() {
int ans = 0;
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
int cnt = 0;
for(int dir=0;dir<4;dir++) {
int ny = i + dy[dir];
int nx = j + dx[dir];
if (ny >= n || ny < 0 || nx >= n || nx < 0)
continue; // 범위를 나갈때
for(int idx=0;idx<4;idx++) {
if(favorite[arr[i][j]][idx]==arr[ny][nx]) {
cnt++;
break;
}
}
}
if(cnt==0)ans+=0;
else if(cnt==1)ans+=1;
else if(cnt==2)ans+=10;
else if(cnt==3)ans+=100;
else if(cnt==4)ans+=1000;
}
}
return ans;
}
}
Author And Source
이 문제에 관하여([백준Java]BOJ21608_상어초등학교), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@zezs3535/백준JavaBOJ21608상어초등학교저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)