Coding - Algo/Java
[백준] 21608번:상어 초등학교 (Java 자바)
jainn
2021. 10. 19. 11:29
728x90
문제
https://www.acmicpc.net/problem/21608
21608번: 상어 초등학교
상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호
www.acmicpc.net
풀이 및 소스코드
구현문제이다.
우선순위큐를 통해 조건에 따른 비교를 수행해주었다.
@Override
public int compareTo(node o) {
if(this.near == o.near) { // 좋아하는 학생 또는 비어있는 칸이 들어가는 near 의 수가 같다면
if(this.x==o.x) { // x (행) 비교. 행이 같다면
return this.y-o.y; // y 비교
}
return this.x-o.x;
}
return o.near-this.near; // near은 내림차순
}
이 우선순위큐에 인접해있는 좋아하는 학생의 좌표(x,y)와 수(near)를 담고,
poll을 했을 때 좋아하는 학생들의 수가 제일 큰 것이 하나라면 바로 그 좌표 값을 그 학생의 자리로 정하고 다음으로 넘긴다.
여러 개라면 그 후보들을 담아 빈 칸의 개수를 조사하러 count_empty() 함수로 보낸다.
count_empty() 함수로 왔으면 해당 후보들의 인접한 비어있는 자리를 count 해 near에 넣는다.
그리고 젤 처음 poll 되는 것이 우리가 찾고자 하는 자리이다.
(이미 우선순위큐 comparable를 사용해서 비교를 해놨기 때문이다.)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Main {
static int n, pown, res;
static int[] info;
static int[][] seat;
static ArrayList<Integer>[] infolist;
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];
pown = (int) Math.pow(n, 2);
info = new int[pown];
infolist = new ArrayList[pown+1];
for(int i=0;i<pown+1;i++) {
infolist[i] = new ArrayList<Integer>();
}
for(int i=0;i<pown;i++) {
st = new StringTokenizer(br.readLine());
info[i] = Integer.parseInt(st.nextToken());
for(int j=0;j<4;j++) {
infolist[info[i]].add(Integer.parseInt(st.nextToken()));
}
}
outer:for(int k=0;k<pown;k++) {
PriorityQueue<node> q = new PriorityQueue<>();
if(k==0) {
seat[1][1] = info[k];
continue;
// 첫번째 사람은 무조건 !
}
if(k==pown-1) {
// 마지막 학생은 남은자리 하나에 넣기
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
if(seat[i][j]==0) {
seat[i][j] = info[k];
break outer;
}
}
}
}
// k인덱스를 가진 학생의 자리탐색 시작
node nowk = count_like(k);
seat[nowk.x][nowk.y] = info[k];
}
// for(int i=0;i<n;i++) {
// for(int j=0;j<n;j++) {
// System.out.print(seat[i][j]+" ");
// }
// System.out.println();
// }
// System.out.println();
count_score();
System.out.println(res);
}
public static node count_like(int k) {
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};
PriorityQueue<node> q = new PriorityQueue<>();
for(int x=0;x<n;x++) {
for(int y=0;y<n;y++) {
if(seat[x][y]!=0) continue;
// 이미 정해진 자리면 검사하지 않아도 된다.
int cnt = 0;
for(int i=0;i<4;i++) {
int nowx = x+dx[i], nowy = y+dy[i];
if(0>nowx||0>nowy||n<=nowx||n<=nowy) continue;
if(infolist[info[k]].contains(seat[nowx][nowy])) cnt++;
}
q.add(new node(x,y,cnt));
}
}
int cnt = 1;
// if(info[k]==7) {
// System.out.println(q.toString()+cnt);
// }
PriorityQueue<node> rq = new PriorityQueue<>();
// 1번을 만족하는 칸이 여러개이면 다음 함수로 넘겨주기 전 만족하는 칸들에 대한 정보를 담아서 리턴한다.
rq.add(q.poll());
int likecount = rq.peek().near;
while(!q.isEmpty()) {
node p_node = q.poll();
if(p_node.near==likecount) {
// 여러개이면 rq에 넣는다.
cnt ++;
rq.add(p_node);
} else {
// 아니면 종료
break;
}
}
// if(info[k]==7) {
// System.out.println(rq.toString()+cnt);
// }
if(cnt==1) {
// 자리가 바로 나오면 리턴
return rq.poll();
} else {
// 바로 자리가 나오지 않으면 2번으로 넘어간다.
return count_empty(rq, k);
}
}
public static node count_empty(PriorityQueue<node> q, int k) {
PriorityQueue<node> rq = new PriorityQueue<>();
// 학생이 놓일 후보 자리값과 인접한 칸 중 비어있는 칸의 카운트를 넣는 우선순위 큐
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};
while(!q.isEmpty()) {
node now_n = q.poll();
int cnt = 0;
for(int i=0;i<4;i++) {
int nowx=now_n.x+dx[i], nowy=now_n.y+dy[i];
if(0>nowx||0>nowy||n<=nowx||n<=nowy) continue;
if(seat[nowx][nowy]==0) cnt++;
}
rq.add(new node(now_n.x, now_n.y, cnt));
}
// if(info[k]==7) {
// System.out.println(rq.toString());
// }
return rq.poll();
}
public static void count_score() {
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};
int[] score = {0, 1, 10, 100, 1000};
for(int x=0;x<n;x++) {
for(int y=0;y<n;y++) {
int cnt = 0;
for(int i=0;i<4;i++) {
int nowx = x+dx[i], nowy = y+dy[i];
if(0>nowx||0>nowy||n<=nowx||n<=nowy) continue;
if(infolist[seat[x][y]].contains(seat[nowx][nowy])) cnt++;
}
res += score[cnt];
}
}
}
}
class node implements Comparable<node>{
int x,y,near;
public node(int x, int y, int near) {
super();
this.x = x;
this.y = y;
this.near = near;
}
@Override
public int compareTo(node o) {
// TODO Auto-generated method stub
if(this.near == o.near) {
if(this.x==o.x) {
return this.y-o.y;
}
return this.x-o.x;
}
return o.near-this.near;
}
@Override
public String toString() {
return "node [x=" + x + ", y=" + y + ", near=" + near + "]";
}
}
반응형