[백준] 21608번:상어 초등학교 (Java 자바)

[백준] 21608번:상어 초등학교 (Java 자바)

728x90

문제

https://www.acmicpc.net/problem/21608

풀이 및 소스코드

구현문제이다.

우선순위큐를 통해 조건에 따른 비교를 수행해주었다.

@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[] 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(); } for(int i=0;i q = new PriorityQueue<>(); if(k==0) { seat[1][1] = info[k]; continue; // 첫번째 사람은 무조건 ! } if(k==pown-1) { // 마지막 학생은 남은자리 하나에 넣기 for(int i=0;i q = new PriorityQueue<>(); for(int x=0;xnowx||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 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 q, int k) { PriorityQueue 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;xnowx||0>nowy||n<=nowx||n<=nowy) continue; if(infolist[seat[x][y]].contains(seat[nowx][nowy])) cnt++; } res += score[cnt]; } } } } class node implements Comparable{ 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 + "]"; } }

반응형

from http://jainn.tistory.com/305 by ccl(A) rewrite - 2021-10-19 13:27:26