글 읽기 - 예외 테스트케이스를 도저히 못찾겠습니다.

badcandy 7년 전 0

벽을 부순 횟수의 오름 차순으로 정렬하고 벽을 부순 횟수가 같을 경우 최단 거리 오름 차순으로 정렬하는 우선순위큐를 이용한 bfs 구현을 했는데

질문에 올라온 예외 테스트케이스와 예제 테스트케이스가 모두 맞습니다.

예외 테스트케이스를 찾지 못하겠네요ㅠㅠ 어떤부분에서 틀렸을까요?

import java.util.PriorityQueue;
import java.util.Scanner;

public class BreakBrick {

	private static int maxY, maxX;
	
	private static int[][] dist;
	
	private static char[][] map;
	
	private static final int[] dy = { -1, 0, 1, 0 };

	private static final int[] dx = { 0, -1, 0, 1 };
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		Scanner sc = new Scanner(System.in);
		
		maxY = sc.nextInt();
		maxX = sc.nextInt();
		
		map = new char[maxY][maxX];
		dist = new int[maxY][maxX];
		
		for (int i = 0; i < maxY; i++) {
			
			String input = sc.next();
			
			for (int j = 0; j < maxX; j++) {
				
				map[i][j] = input.charAt(j);
				dist[i][j] = -1;
			}
		}
		
		int ret = find();
		
		System.out.println(ret == 0 || ret == 1 ? dist[maxY - 1][maxX - 1] + 1 : -1);
	}
	
	private static int find() {
		// 벽을 부순 횟수의 오름 차순으로 정렬하고 벽을 부순 횟수가 같을 경우 최단 거리 오름 차순으로 정렬한다.
		// 우선순위큐를 이용할 경우 더 빠르게 탐색이 가능
        PriorityQueue<Point> pq = new PriorityQueue<>();
		
		pq.add(new Point(0, 0, 0, 0));
		
		dist[0][0] = 0;
		
		while (!pq.isEmpty()) {
			
			int hereY = pq.peek().y;
			int hereX = pq.peek().x;
			int count = pq.remove().count;
			
			if (hereY == maxY - 1 && hereX == maxX - 1)	return count;
			
			for (int i = 0; i < 4; i++) {
				
				int nextY = hereY + dy[i];
				int nextX = hereX + dx[i];
				int nextCount = count;
				
				if (nextY >= 0 && nextX >= 0 && nextY < maxY && nextX < maxX) {
					
                    // 방문하지 않았던 위치일 때
					if (dist[nextY][nextX] == -1) {
						
                        // 벽을 부수면
						if (map[nextY][nextX] == '1') {
							// 벽 부순 카운트를 증가
							++nextCount; 
						}
						// 이동한 거리를 증가
						dist[nextY][nextX] = dist[hereY][hereX] + 1;
						// 우선순위큐에 넣는다.
						pq.add(new Point(nextY, nextX, nextCount, dist[nextY][nextX]));
					}
				}
			}
		}
		
		return -1;
	}
   
	private static class Point implements Comparable<Point>{

		public int y, x, count, dist;

		public Point(int y, int x, int count, int dist) {
			super();
			this.y = y;
			this.x = x;
			this.count = count;
			this.dist = dist;
		}

		@Override
		public int compareTo(Point o) {
			// TODO Auto-generated method stub
			int ret = Integer.compare(this.count, o.count);
			
			if (ret == 0) {
				
				return Integer.compare(this.dist, o.dist);
			}
			
			return ret;
		}
	}
}

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

문제

문제

출처

ICPC

예외 테스트케이스를 도저히 못찾겠습니다.

badcandy 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말