글 읽기 - 반례를 못찾겠습니다... 도와주세요ㅜㅜ

wkddbswjd325 5년 전 0

코딩을 잘 하는 것이 아니라 그냥 제 방식대로 조금 풀어봤는데요..

이클립스에서 테스트케이스와 여러가지 반례를 넣었는데 모두 제대로 된 아웃풋이 나와서 제출해보았는데 계속 틀렸다고 나오네요..

채점중도 뜨지 않는것을 보면 기본적인 것을 놓친 것 같은데ㅜㅜ 무엇을 놓쳤는지 아무리 봐도 모르겠네요ㅠㅠ

혼자 열심히 고민해봤는데 정말로 모르겠어서 질문합니다ㅠㅜ 도와주세요ㅠㅠ

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	
	static int n;
	static int[][] space;

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		@SuppressWarnings("resource")
		Scanner scan = new Scanner(System.in);
		
		n = scan.nextInt();
		space = new int[n][n];
				
		int x = -1, y = -1;
		
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				space[i][j] = scan.nextInt();
				
				if(space[i][j] == 9) {
					x = i;
					y = j;
				}
			}
		}
		
		solve(x, y);
		
	
	}

	public static void solve(int i, int j) {
		// TODO Auto-generated method stub
		
		int time = 0;
		
		int shark = 2;
		int eating = 0;
		
		space[i][j] = 0;
		
		boolean[][] isVisited = new boolean[n][n];
		int[][] dist = new int[n][n];
		Queue<Integer> qx = new LinkedList<Integer>();
		Queue<Integer> qy = new LinkedList<Integer>();
		
		Queue<Integer> qa = new LinkedList<Integer>();
		Queue<Integer> qb = new LinkedList<Integer>();
		
		int[] dx = {-1, 0, 0, 1};
		int[] dy = {0, -1, 1, 0};
		
		while(true) {
			
			for(int a=0;a<n;a++) {
	            for(int b=0;b<n;b++)
	                isVisited[a][b] = false;
	        }
			
			for(int a=0;a<n;a++) {
	            for(int b=0;b<n;b++)
	                dist[a][b] = 0;
	        }
		
			int fish = 0;
			qa.clear();
			qb.clear();
			
			
			qx.add(i);
			qy.add(j);
			isVisited[i][j] = true;
			int limit = 0;
			
			while(!qx.isEmpty() && !qy.isEmpty()) {
				int x = qx.poll();
				int y = qy.poll();
				
				if(dist[x][y] != 0 && dist[x][y] == limit) break;
				
				for(int k = 0; k < 4; k++) {
					int a = x + dx[k];
					int b = y + dy[k];
					
					if(a<0 || b<0 || a>=n || b>=n) continue;
						
					if(!isVisited[a][b] && space[a][b] <= shark && space[a][b] >= 0) {
						
						qx.add(a);
						qy.add(b);
						isVisited[a][b] = true;
						dist[a][b] = dist[x][y] + 1;
						
						if(space[a][b] != 0 && space[a][b] != shark) {
							limit = dist[a][b];
							fish++;
							qa.add(a);
							qb.add(b);
						}
						
					}
				}	
					
				
			}	
				
			if(fish <= 0) break;
			
			int[][] fishes = new int[fish][2];
			int temp=0;
			while(!qa.isEmpty() && !qb.isEmpty()) {
				fishes[temp][0] = qa.poll();
				fishes[temp][1] = qb.poll();
				temp++;
			}
			
			int min = 100;
			int min_idx = 0;
			for(int idx = 0; idx < fish; idx++) {
				if(fishes[idx][0] < min) {
					min = fishes[idx][0];
					min_idx = idx;
				}
			}
			
			int x = fishes[min_idx][0];
			int y = fishes[min_idx][1];
			
			eating++;
			space[x][y] = 0;

			if(shark == eating) {  
				shark++;
				eating = 0;		
			}
			
			time += dist[x][y];
			
			i = x;
			j = y;
			qx.clear();
			qy.clear();
			
		}	

		System.out.println(time);
	}

	

}

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

문제

문제

출처

ICPC

반례를 못찾겠습니다... 도와주세요ㅜㅜ

wkddbswjd325 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말