[JAVA][伯俊17143]釣り王
69415 ワード
質問する
釣り王釣りの場所の大きさはRです×C字格板で表すことができます.グリッドボードの各セルは(r,c)で表すことができます.rは行、cは列、(R,C)は下図の右下隅のセルです.格子の中にはサメが1匹までいます.サメには大きさと速度がある.
釣り王は最初は1番列の左側の部屋にいました.次は1秒以内に起こったことで、次のような順番で起こります.釣り王は一番右の列の右の格に移動すると移動を停止します.
釣り王は右に1格移動した.
釣り王がいる10匹のサメのうち、最も近いサメを捕獲した.サメを捕まえると、格子板から捕まえたサメが消えてしまいます.
サメが動いています.
サメは入力された速度で所定の速度で移動し、速度の単位は格/秒である.サメが移動するセルがグリッドプレートの境界を超えている場合は、逆方向に移動し、速度を維持します.
左図の状態では、1秒後に右図の状態になります.サメが見た方向は速度の方向で、左下に書かれた整数は速度です.左上にサメを区別する文字を書きました.
サメが移動した後、1部屋にサメが2匹以上いることができます.このとき、最大のサメは残りのサメを全部食べます.
钓り王钓りサメの格板状态をタイミングに、钓り王钓りサメの大きさの和を得る.
入力
最初の行は、メッシュプレートのサイズR、C、およびサメの数Mを与える.(2 ≤ R, C ≤ 100, 0 ≤ M ≤ R×C)
2行目から、Mラインにサメの情報が.サメの情報は5つの整数r,c,s,d,z(1≦r≦r,1≦c≦C,0≦s≦1000,1≦d≦4,1≦z≦10000)からなる.(r,c)はサメの位置,sは速度,dは移動方向,zは大きさである.dが1の場合は上,2の場合は下,3の場合は右,4の場合は左である.
同じ大きさのサメは2匹もいません.1つの格子に2匹以上のサメはいません.
しゅつりょく
釣り王が捕獲したサメの大きさの和を出力します.
✨ Methodology
問題を読んで、私が思いついた答え方
1.サメ類
またサメ類を作成して入力を受ける場合は,M本のサメの情報を配列に格納する.
public static class Shark{
int r;
int c;
int speed;
int direction;//1상2하3우4좌
int size;
//초기 initializing
public Shark(int r, int c, int speed, int direction, int size) {
this.r =r;
this.c = c;
this.speed= speed;
this.size = size;
this.direction = direction;
}
}
2.アレイ方向
質問では、dが1の場合は上、2の場合は下、3の場合は右、4の場合は左と表示されるので、Direction配列は「上、下、右、左」と表示されます.
static int[][] dd= {{0,0},{-1,0},{1,0},{0,1},{0,-1}};//상하우좌
方向を変えると、preference directionの場合:上(1)->下->2(+1)に切り替える必要があります
prevery direction:下(2)->上の場合は、->1(-1)を置き換える必要があります.
preference direction:右(3)->左->4(+1)に切り替える必要がある場合
if prevery direction:左(4)->右->3(-1)
上のように直接書くと、法則性が見つかります.
したがって,偶数方向->1,奇数方向->+1で方向が反転する.
3.サメの予想移動位置
個人的にはこの問題はシミュレーションから転換できないと思います.
2匹目のサメを移動したが、移動した場所に移動していない3匹目のサメがいると、それに関連する処理が面倒になる.そこで考えたのは、前に作成したShark型リストに格納されている位置だけサメの位置を計算してから、シミュレーションを迂回することです.
そのため、予めリストにサメの新しい座標を更新してサメの予想移動位置を計算する場合は、配列範囲から外れた場合に注意するだけでよい.
へんすう
int move = sharks.get(i).speed;// 상어는 speed 만큼 움직인다
int nr = sharks.get(i).r;//row 좌표를 계산할 변수
int nc = sharks.get(i).c;//col 좌표를 계산할 변수
サメは1秒ごとに同じ速度で移動できます.従って,1秒のmove変数にサメの移動の格数(speed)を格納し,speedをwhileゲートから減少させ,移動の機会が0になるまでnrとncを計算する.ドア
サメは1秒以内に上記の移動に従って移動座標を移動しなければならない.
サメが移動するたびに
nr += dd[sharks.get(i).direction][0];
nc += dd[sharks.get(i).direction][1];
動くだけ動く.shark.get(i).方向はサメの移動方向なのでdd[方向][0]はr座標、dd[方向][1]はc座標です.移動が終了したらnrとncの範囲をチェックし、nrとncの範囲が配列範囲を超えている場合は移動できないセルが移動しているため、方向を変えて2つのセルを移動することができます.//움직이고 난 후에 범위가 넘었을 경우:
if(nr<1||nc<1||nr>=R+1||nc>=C+1) {
//방향 전환:
if(sharks.get(i).direction%2 ==0){sharks.get(i).direction-=1;}
else{sharks.get(i).direction+=1;}
//이미 움직여버렸기때문에 반대 방향으로 두칸 이동해줘야함
nr += dd[sharks.get(i).direction][0]*2;
nc += dd[sharks.get(i).direction][1]*2;
}
移動が終わったら、最後に更新したnrとnc値をサメに適用すればいいです.4.シミュレーション
サメの位置配列が更新された場合は、地図を初期化し、リストに保存されているサメを元の場所に戻すことができます.
配列にサメのインデックスを保存すると、サイズを比較しやすくなり、釣り人がどんなサメを釣ったのかを説明しやすくなります.インデックス番号ではなくサメのサイズを入れると、後でもっと大きなサメが同じ位置に来ると、修正できない事故が発生します.
このとき、サメの位置を外すにはすでにサメがいるので、2つのサイズを比較して、より小さなサメを配列(0,0)に移動し、リストでサメの位置(0,0)を更新します.
リストから削除しない理由は,最初にリストから削除した後,index--,i++などを処理したが,Baek Junの最後のテストケースで問題が見られたためである.
サメをリストから外すとサメのインデックスが減少するので、配列の中に2つのインデックスのサメがいるのを見ました.そのため、サメをリストから外すのではなく、サメをアレイの外に送る方法を選んだ.
配列中の(0,0)に移動するので、前述のサメの予想位置方法では、
if(nr == 0 || nc==0) continue outer;
処理してくれれば、次のサメに入ります.この処理を行わないと、サメが-1に移動しarrayindexoutboundエラーが発生する可能性があります.処理する必要があります.for(int i =1; i<index; i++) {
int r = sharks.get(i).r;//상어의 r 위치
int c = sharks.get(i).c;//상어의 c 위치
//사이즈가 아니라 현재 상어의 인덱스를 넣는다! 사이즈를 넣으면 후에 더 큰 상어가 오면 문제생김
if(arr[r][c]==0) {arr[r][c] = i;}//상어가 없으면 그냥 넣어도 된다
else if(arr[r][c]!=0) { //상어가 이미 있다
if(sharks.get(arr[r][c]).size>sharks.get(i).size){//기존상어가 더 큼
sharks.get(i).c = 0;
sharks.get(i).r = 0;
}
else {//현재 상어가 더 크다!
int eaten = arr[r][c];//잡아먹힌 상어
sharks.get(eaten).c = 0;
sharks.get(eaten).r = 0;
arr[r][c] = i;//큰 상어가 살아 남았다
}
}
}
5.釣り人が釣ったサメ
釣り人は総c(列)秒を移動し、t=1で配置し、whileサイクルでt
//메인 메서드 내의 틀:
int answer = 0; //상어의 사이즈를 더할 변수
validateLocation();//입력을 받은 직후 상어를 물에 풀어준다
int t = 0; //t는 0부터 시작해서 열(time)과 같아질 때 까지 낚시를 한다
int time = C;//낚시꾼은 열을 이동하며 낚시를 하며, 열의 끝에오면 낚시가끝난다-> time== Column
while(t<time){
t++;//time == 낚시꾼의 위치
answer+=caught(t); //1. 낚시왕이 오른쪽으로 한칸 이동하며 낚시한다
swim(); //2. 상어의 예상 위치 계산
validateLocation();//3. 상어 맵에 배치
}
釣り人がt秒で釣ったサメは、回転配列でarr[i][t秒]が0でない場合、すなわちサメが存在する場合、サメの大きさを正解に加えてサメリストからサメを除去すればよい.また、釣り人は一番前のt列のサメしか捕まえられないので、一番近いサメを捕まえさえすれば、探索を止めるべきです./**낚시꾼이 t초에 잡은 상어*/
private static int caught(int t) {
int caught = 0;
for(int i = 1; i <=R; i++) {//C는 고정--as t
if(arr[i][t]!=0) {//가장 가까운 상어 발견 -> arr에는 상어의 index가 저장되어있다
caught= sharks.get(arr[i][t]).size; //상어의 크기 리턴
sharks.remove(arr[i][t]); //상어 리스트에서 상어는 빼준다
arr[i][t] = 0;
return caught;
}
}
return caught;//해당 열에 상어가 없다면 0 리턴
}
すべてのソース
MapInfo()とSharkLocationInfo()は、シミュレーション時にサメや地図の現状をよりよく理解するためのユーティリティです.地図やサメの状態を見たい場合は、コメントをキャンセルすることができます.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
public class 백준_17143_낚시왕 {
public static class Shark{
int r;
int c;
int speed;
int direction;//1상2하3우4좌
int size;
//초기 initializing
public Shark(int r, int c, int speed, int direction, int size) {
this.r =r;
this.c = c;
this.speed= speed;
this.size = size;
this.direction = direction;
}
}
static ArrayList<Shark> sharks;//상어의 정보를 저장할 배열
static int[][] dd= {{0,0},{-1,0},{1,0},{0,1},{0,-1}};//상하우좌
static int R,C,time,arr[][];
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
R = Integer.parseInt(st.nextToken());
C = time = Integer.parseInt(st.nextToken());//time: 총 열만큼 움직이고 마지막 열에서 끝나기 때문에 time== C
int M = Integer.parseInt(st.nextToken());//상어의 수
if(M==0) {System.out.println("0");return;}
arr = new int[R+1][C+1];
sharks = new ArrayList<>();
sharks.add(new Shark(0,0,0,0,0));//dummy data
for(int m = 0; m<M ; m++) {//상어의 수만큼 정보 들어온다
//at 0초:
st = new StringTokenizer(br.readLine());
int r = Integer.parseInt(st.nextToken());//상어 r 좌표
int c = Integer.parseInt(st.nextToken());//상어 c 좌표
int s = Integer.parseInt(st.nextToken());//speed
int d = Integer.parseInt(st.nextToken());//direction
int z = Integer.parseInt(st.nextToken());//size
sharks.add(new Shark(r,c,s,d,z));
}//end of input
int answer = 0;
int t =0;
validateLocation();//initiate
// MapInfo();
while(t<time) {
t++;
// System.out.println("낚시 start");
answer += caught(t);//낚시꾼이 먼저 잡고
// SharkLocationInfo();
// MapInfo();
// System.out.printf("after %d초: ",t);
// System.out.println("상어가 수영했다");
swim();//상어 이동위치 잡고
// SharkLocationInfo();
// System.out.println("validate 후 맵에 추가");
validateLocation();//상어 옮기고
// SharkLocationInfo();
// MapInfo();
}
System.out.println(answer);
}//end of main
/**3. 낚시꾼이 t초에 잡은 상어*/
private static int caught(int t) {
int caught = 0;
for(int i = 1; i <=R; i++) {//C는 고정--as t
if(arr[i][t]!=0) {//상어가 있다면 그 상어의
//arr[][]에는 상어의 인덱스가 담겨져 있다
caught= sharks.get(arr[i][t]).size;
sharks.remove(arr[i][t]);
arr[i][t] = 0;
return caught;
}
}
return caught;
}
/** 2. 상어를 맵에 배치 :1번 메소드에서 업데이트된 상어 위치를 기반으로,
해당 위치에 상어 두마리 이상인지 확인하고 크기가 큰 상어만 배치한다.*/
private static void validateLocation() {
//배열 초기화:
for(int i= 0 ;i<=R; i++) {
for(int j =0; j<=C ;j++) {
arr[i][j] = 0;
}
}
int index = sharks.size();
for(int i =1; i<index; i++) {
int r = sharks.get(i).r;//상어의 r 위치
int c = sharks.get(i).c;//상어의 c 위치
// System.out.printf("%d , %d 상어 생성\n",r,c);//확인용
if(arr[r][c]==0) {//상어가 없다면 그냥 넣어도 된다
arr[r][c] = i;//사이즈가 아니라 현재 상어의 인덱스를 넣는다! 사이즈를 넣으면 후에 더 큰 상어가 오면 문제생김
}
else if(arr[r][c]!=0) {
// System.out.println("현재 위치에 상어가 이미 있다");
if(sharks.get(arr[r][c]).size>sharks.get(i).size) {
// System.out.println(i+"번째 상어는 퇴출한다 -> 기존애 사이즈가 더 커서 ");
//sharks.remove(i);//작은 상어는 퇴출..하지말고 0,0으로 보내야 문제 발생 x
sharks.get(i).c = 0;//먹힌 상어들의 좌표를 0,0으로 지정
sharks.get(i).r = 0;//먹힌 상어들의 좌표를 0,0으로 지정
}
else {//현재 상어가 더 크다!
int eaten = arr[r][c];//잡아먹힌 상어
sharks.get(eaten).c = 0;//0,0으로 지정
sharks.get(eaten).r = 0;//0,0으로 지정
arr[r][c] = i;//큰 상어가 살아 남았다
}
}
}
//배열 채워짐
}
/**1번 메서드: 상어의 예상 이동 위치를 상어 배열에 업데이트 시킨다.*/
private static void swim() {
outer: for(int i = 0; i< sharks.size() ;i ++) {
//원래 좌표: System.out.printf("Previous Location: %d,%d\n",sharks.get(i).r,sharks.get(i).c);
int move = sharks.get(i).speed;//이만큼 움직여야 한다
int nr = sharks.get(i).r;//새 위치 //row: y좌표
int nc = sharks.get(i).c;//새 위치//col: x좌표
if(nr == 0 || nc==0) continue outer; //먹힌 상어들은 무시하고 다음 i로 이동
while (move>0) {
nr += dd[sharks.get(i).direction][0];//dd[방향][r표시]
nc += dd[sharks.get(i).direction][1];//dd[방향][c표시]
//움직이고 나서:
if(nr<1||nc<1||nr>=R+1||nc>=C+1) {//범위를 넘겼을 경우:
if(sharks.get(i).direction%2 ==0){sharks.get(i).direction-=1;}//짝수일 경우 -1
else{sharks.get(i).direction+=1;}//홀수일 경우 +1
nr += dd[sharks.get(i).direction][0]*2;//이미 움직여서는 안되는 곳까지 움직였기 때문에 반대 방향으로 두칸 이동
nc += dd[sharks.get(i).direction][1]*2;
}
move--;
}
//위 while 끝나면 nx 와 ny 를 다시 상어 위치로 업데이트
sharks.get(i).r = nr;
sharks.get(i).c = nc;
//새 좌표 확인: System.out.printf("new location: %d, %d\n",nr,nc);
}
}
//Utilities
/**상어 리스트에서 남은 상어들의 정보를 확인한다*/
public static void SharkLocationInfo() {
/*상어 위치 정보: */
System.out.println("상어 위치 정보");
System.out.println("+-----------+----------------+------------+");
for(int i =0; i< sharks.size() ; i++) {
System.out.println("index "+i+" : "+ sharks.get(i).r+" , "+sharks.get(i).c);
}
}
/**현재 배열의 상태를 출력한다*/
public static void MapInfo() {
System.out.println("현재 맵: ");
for(int i =1; i<=R; i++) {
for(int j = 1; j<=C; j++) {
System.out.print(arr[i][j]+" ");
}
System.out.println();
}//배열 체크
}
}
学んだこと
方向の並びがもっと良くなったようです.最初の方法学から逸脱することなく,コードを記述し,この方法を実践するために,最初の考え方から多く修正した.
この問題はずいぶん時間がかかったが,今度はもう少し時間を縮めたい
Reference
この問題について([JAVA][伯俊17143]釣り王), 我々は、より多くの情報をここで見つけました https://velog.io/@junbee/JAVA백준-17143-낚시왕テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol