글 읽기 - 반례 다 통과했는데 어디가 문제일까요

kwy2868 5년 전 0

주어진 테스트케이스, 질문에 있는 반례들 모두 맞게 나오는 것 같은데 오답 처리 되네요ㅜㅜ

어디가 문제일까요..?

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

public class Main {
	static ArrayList<Fish> fishList;
	static int[][] map;
	static int[][] visited;
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int N = scanner.nextInt();
		map = new int[N][N];
		visited = new int[N][N];
		int[] dr = {-1, 0, 0, 1};
		int[] dc = {0, -1, 1, 0};
		
		int answer = 0;
		int minSize = Integer.MAX_VALUE;
		int eatCount = 0;
		
		Fish fish = null;
		fishList = new ArrayList<Fish>();
		for(int row=0; row<N; row++) {
			for(int col=0; col<N; col++) {
				map[row][col] = scanner.nextInt();
				if(map[row][col] == 9) {
					fish = new Fish(row, col, 2);
					map[row][col] = 0;
				}
				else if(map[row][col] != 0) {
					Fish f = new Fish(row, col, map[row][col]);
					if(minSize > map[row][col])
						minSize = map[row][col];
					fishList.add(f);
				}
			}
		}
		
		if(minSize >= 2) {
			System.out.println(0);
			return;
		}
			
		int startRow = fish.row;
		int startCol = fish.col;
		
		for(int i=0; i<N; i++)
			Arrays.fill(visited[i], -1);
		Queue<Integer> queue = new LinkedList<Integer>();
		queue.add(startRow);
		queue.add(startCol);
		visited[startRow][startCol] = 0;
		
		ArrayList<Fish> eatable = new ArrayList<Fish>();
		while(!queue.isEmpty()) {
			if(minSize >= fish.size)
				break;
			int r = queue.remove();
			int c = queue.remove();
//			System.out.println(r + " " + c);
			for(int i=0; i<4; i++) {
				int nr = r + dr[i];
				int nc = c + dc[i];
				if(nr < 0 || nc < 0 || nr > N-1 || nc > N-1)
					continue;
				if(map[nr][nc] == 0 || map[nr][nc] == fish.size) {
					if(visited[nr][nc] == -1) {
						queue.add(nr);
						queue.add(nc);
						visited[nr][nc] = visited[r][c] + 1;
					}
				}
				else {
					if(fish.size > map[nr][nc]) {
						if(visited[nr][nc] == -1) {
							visited[nr][nc] = visited[r][c] + 1;
							for(int j=0; j<fishList.size(); j++) {
								Fish f = fishList.get(j);
								if(f.row == nr && f.col == nc) {
									f.distance = visited[r][c] + 1;
									eatable.add(f);
									break;
								}
							}
						}
					}
				}
			}
			if(queue.isEmpty()) {
				Fish eated = eat(eatable);
				if(eated == null)
					break;
				answer += eated.distance;
				eatCount++;
				if(eatCount == fish.size) {
					fish.size++;
					eatCount = 0;
				}
				
				map[eated.row][eated.col] = 0;
				fish.row = eated.row;
				fish.col = eated.col;
				for(int j=0; j<N; j++)
					Arrays.fill(visited[j], -1);
				
				queue.add(fish.row);
				queue.add(fish.col);
				visited[fish.row][fish.col] = 0;
				minSize = minCheck();
				eatable = new ArrayList<Fish>();
				fishList.remove(eated);
			}
		}
		System.out.println(answer);
	}
	
	public static Fish eat(ArrayList<Fish> eatable) {
		Fish fish = null;
		sort();
		if(eatable.size() == 0)
			return null;
		fish = eatable.get(0);
		int min = fish.distance;
		int tempRow = fish.row;
		int tempCol = fish.col;
		for(int i=1; i<eatable.size(); i++) {
			Fish f = eatable.get(i);
			if(f.distance == min) {
				if(tempRow > f.row) {
					fish = f;
				}
				else if(tempRow == f.row) {
					if(tempCol > f.col)
						fish = f;
				}
			}
		}
		return fish;
	}
	
	public static void sort() {
		// sort fishList by dist
		for(int i=0; i<fishList.size(); i++) {
			for(int j=0; i+j+1<fishList.size(); j++) {
				Fish fish1 = fishList.get(j);
				Fish fish2 = fishList.get(j+1);
				Fish temp;
				if(fish1.distance > fish2.distance) {
					temp = fish1;
					fishList.set(j, fish2);
					fishList.set(j+1, temp);
				}
			}
		}
	}
	public static int minCheck() {
		int min = Integer.MAX_VALUE;
		for(int i=0; i<fishList.size(); i++) {
			if(min > fishList.get(i).size)
				min = fishList.get(i).size;
		}
		return min;
	}
}
class Fish{
	int row;
	int col;
	int size;
	int distance;
	
	Fish(int row, int col, int size){
		this.row = row;
		this.col = col;
		this.size = size;
	}
}

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

문제

문제

출처

ICPC

반례 다 통과했는데 어디가 문제일까요

kwy2868 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말