글 읽기 - 33%에서 틀리는... 아기상어씨....ㅠㅠ...뭐가 문제일까요?

txtcopy 5년 전 0

질문 글 전체 다읽어보고 테스트 케이스 전부 돌려보고..

순서도 체크해보고...이것저것 다해봤는데...안돼네요...ㅠㅠㅠㅠㅠ 33%에서 계속 틀렸습니다가 나옵니다...

ㅠㅠㅠ하 뭐가 문제일까요?

반례도 모르겠고...

갓님들...잠깐 시간내서 봐주실수있나요 ?

감사합니다 ㅠㅠ

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;


class fishPoint implements Comparable<fishPoint>{
	int x;
	int y; 
	int distance;
	int fishSize;
	int originX;
	int originY;
	fishPoint(int y, int x, int distance, int fishSize){
		this.x = x; 
		this.y = y;
		this.distance = distance;
		this.fishSize = fishSize;

	}
	@Override
	public int compareTo(fishPoint target) {
          return this.distance <= target.distance ? -1: 1;
	}
}
class sharkPoint{
	int x;
	int y;
	int sharkSize; 
	int distance;
	sharkPoint(int y, int x, int distance){
		this.x = x;
		this.y = y;
		//this.sharkSize =  sharkSize;
		this.distance = distance;
	}
}
public class Main {
	static int MAP[][] = new int[21][21];
	static boolean visited[][] = new boolean[21][21];
	static Queue <sharkPoint> q = new LinkedList<sharkPoint>();
	static ArrayList<fishPoint> fArr = new ArrayList<fishPoint>();
	static int EATMAP[][] = new int[21][21];
	static int N;
	static int CNT = 0;
	static int EATSEQ= 0;
	static int TIME;
	static int[] dx = { 1, -1, 0, 0 };
	static int[] dy = { 0, 0, 1, -1 }; 
	static int originX;
	static int originY;
	static int sharkSize = 2 ;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		for(int i = 0 ; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int idx = 0; 
			while(st.hasMoreTokens()) {
				MAP[i][idx] = Integer.parseInt(st.nextToken());
				if(MAP[i][idx] == 9) {
					
					originY = i;
					originX = idx;
				
					q.add( new sharkPoint(i ,idx,  0) );
				}

				idx+=1;
			}
		}
		

		//printMap();
		bfs();
		//printMap();
//		printeatMap();
//		System.out.println(distance);
		System.out.println(TIME);
	}
	public static void printMap() {
		for(int i= 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				System.out.print(MAP[i][j] + " ");
			}
			System.out.println();
		}
	}

	public static void printeatMap() {
		for(int i= 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				System.out.print(EATMAP[i][j] + " ");
			}
			System.out.println();
		}
	}
	
	
	
	
	/*
	 * 더 이상 먹을 수 있는 물고기가 공간에 없다면 
	 * 아기 상어는 엄마 상어에게 도움을 요청한다.
		먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
		먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.
		거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최소값이다.
		거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 
		그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.
	 */
	public static void bfs() {
		while(true) {
			//printMap();
			//System.out.println();
			boolean EAT = false;
			while(!q.isEmpty()) {
				int distance = 0;
				int qSize = q.size();
				for(int s = 0 ; s < qSize ; s++) {
					sharkPoint sp = q.poll();
					visited[sp.y][sp.x] = true;
					distance = sp.distance;
					distance += 1;
					for(int d = 0 ; d < 4; d ++) {
						int yy = sp.y + dy[d];
						int xx = sp.x + dx[d];
						if( yy >= 0 && yy < N && xx >= 0 && xx < N ) {
							if( !visited[yy][xx] && MAP[yy][xx] <= sharkSize ) {
								//System.out.println("q add 합니다 yy= " + yy + " xx = " + xx + " 거리 " + distance);
								q.add(new sharkPoint(yy, xx, distance ));
								visited[yy][xx] = true;
								if( MAP[yy][xx] < sharkSize && MAP[yy][xx] != 0 ) { //상어 크기 보다 작으면 
									//System.out.println("Farr add 합니다 yy= " + yy + " xx = " + xx + " 거리 " + distance);
									fArr.add(new fishPoint(yy, xx, distance , MAP[yy][xx]));
									EAT = true;
								}
							}
						}
					}
				}
			}
			if(EAT) {
				//만약에 하나면
				if(fArr.size() == 1) {
					//먹음 
					fishPoint fp = fArr.get(0);  //가장 디스턴스가 짧은 친구 
					MAP[originY][originX] = 0; 
					//MAP[fp.y][fp.x] = 9;
					originX = fp.x;
					originY = fp.y;
					
					CNT +=1;
					EATSEQ +=1; //순서 체크용
					if(CNT % sharkSize == 0) {
						sharkSize += 1;
						CNT = 0;
					}
					TIME += fp.distance;
					//현재 상어 위치 세팅
					q.add(new sharkPoint(fp.y, fp.x, 0));
					EATMAP[fp.y][fp.x] = EATSEQ; //순서 체크용
					fArr.clear(); //fArrClear;
					visited = new boolean[21][21];
					
				}
				//여러개 면
				else if(fArr.size() > 1){
					Collections.sort(fArr);
					fishPoint fp = fArr.get(0);  //가장 디스턴스가 짧은 친구 
					int minX = 999;
					int minY = 999;
					for(int i = 0 ; i < fArr.size(); i++) {
						if( fp.distance != fArr.get(i).distance ) { //다른게 나오는 순간 종료 
							break;
						}
						fishPoint target = fArr.get(i);
						//가장 위에 있어야함
						if( minY > target.y) {
							minY = target.y; 
							minX = target.x;
							if(minX > target.x) {
								minY = target.y; 
								minX = target.x;		
							}
						}
						//System.out.println(fArr.get(i).y + " " + fArr.get(i).x + " "+ fArr.get(i).distance);
					}
					
					//System.out.println("현재 FARR에서 제일 작은 값 " + minY + " " + minX);
					MAP[originY][originX] = 0; 
					//MAP[minY][minX] = 9;
					originX = minX;
					originY = minY;
					
					CNT +=1;
					EATSEQ+=1; //순서 체크용
					if(CNT % sharkSize == 0) {
						sharkSize += 1;
						CNT = 0;
					}
					
					//현재 상어 위치 세팅
					q.add(new sharkPoint(minY, minX, 0));
					EATMAP[minY][minX] = EATSEQ; //순서 체크용
					fArr.clear(); //fArrClear;
					visited = new boolean[21][21];
					TIME += fp.distance;
				}
			}else {// 끝
				return;
			}
		}
	}
}

lemidia 4년 전 0

너무 늦은 답변이 아닐지 모르겠으나.. 아직 성공 못하셔서 답글 남겨요.

확인해 봤는데 우선순위 때문에 그런거구요

30-32 부분에 우선순위를 거리 뿐 만 아니라 행과 열에 대해서도 부여해주셔야 합니다.

아랫부분에 30-32행 수정한 소스 첨부하겠습니다.

고쳤더니 맞았습니다.

@Override
    public int compareTo(fishPoint target) {
        if (this.distance == target.distance){
            if (this.y == target.y){
                return this.x < target.x ? -1 : 1;
            }else if (this.y < target.y)
                return -1;
            else
                return 1;
        }else if (this.distance < target.distance)
            return -1;
        else
            return 1;
    }

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

33%에서 틀리는... 아기상어씨....ㅠㅠ...뭐가 문제일까요?

txtcopy 5년 전 0

lemidia 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말