글 읽기 - 7%정도에서 틀리는데 반례나 조언 부탁드립니다.

bamboo_703 3년 전 0

예제 케이스나 질문 검색에 있는 반례도 입력해보았는데 정답은 다 맞는 것 같습니다.

어느부분에서 틀리는지 감이 안잡혀서 질문 드립니다 ㅠㅠ

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

class loca{
	int x; int y;
	loca(int x, int y){
		this.x = x; this.y = y;
	}
}

public class Main {
	
	static int n;
	static int m;
	static boolean tf=true;
	public static void main(String[] args) throws Exception{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		Queue<loca> queue = new LinkedList<loca>();
		
		String a = br.readLine();
		String[] StrA = a.split(" ");
		n = Integer.parseInt(StrA[0]);
		m = Integer.parseInt(StrA[1]);
		int fuel = Integer.parseInt(StrA[2]);
		
		int[][] map = new int[n][n];
		int[][] check = new int[n][n]; // bfs 하면서 이동거리 확인
		
		for(int i=0; i<n; i++) { // 지도 표시
			String b = br.readLine();
			String[] StrB = b.split(" ");
			
			for(int j=0; j<n; j++) {
				map[i][j] = Integer.parseInt(StrB[j]);
			}
		}
		String c = br.readLine();
		String[] StrC = c.split(" ");
		int taxi_x = Integer.parseInt(StrC[0]);
		int taxi_y = Integer.parseInt(StrC[1]);
		loca taxi = new loca(taxi_x-1, taxi_y-1); // 택시 시작점 offer
		queue.offer(taxi);
		
		loca[] arrive = new loca[m+2];
		for(int i=0; i<m+2; i++) {
			loca ive = new loca(0, 0);
			arrive[i] = ive;
		}
		
		for(int i=0; i<m; i++) { // 승객 정보 입력
			String d = br.readLine();
			String[] StrD = d.split(" ");
			
			int x = Integer.parseInt(StrD[0]);
			int y = Integer.parseInt(StrD[1]);
			int dx = Integer.parseInt(StrD[2]);
			int dy = Integer.parseInt(StrD[3]);
			
			map[x-1][y-1] = i+2; // 지도에 승객 위치 표시
			arrive[i+2].x = dx-1; arrive[i+2].y = dy-1; // 승객별 도착지 저장
		}
		
		for(int i=0; i<m; i++) {
			loca goal = new loca(-1, -1);
			for(int arr[] : check)
				Arrays.fill(arr, 0);
			while(!queue.isEmpty()) { // 가까운 승객 찾기
				loca temp = queue.poll();
				if(map[temp.x][temp.y]>1) { // 승객 탑승
					int k = map[temp.x][temp.y];
					goal.x = arrive[k].x; goal.y = arrive[k].y; // 도착지 확인
					fuel -= check[temp.x][temp.y];
					if(fuel<0) tf=false;
					queue.clear(); queue.offer(temp); // 큐 clear 및 현 위치 offer
					map[temp.x][temp.y] = 0; // 탑승한 승객 위치는 0으로 초기화
					break;
				}
				// 더 작은 행 >> 더 작은 열 우선 탐색
				if(temp.x>0 && check[temp.x-1][temp.y]==0 && map[temp.x-1][temp.y]!=1 ) {
					loca push = new loca(temp.x-1, temp.y);
					queue.offer(push); check[temp.x-1][temp.y] = check[temp.x][temp.y]+1;
				}
				if(temp.y>0 && check[temp.x][temp.y-1]==0 && map[temp.x][temp.y-1]!=1 ) {
					loca push = new loca(temp.x, temp.y-1);
					queue.offer(push); check[temp.x][temp.y-1] = check[temp.x][temp.y]+1;
				}
				if(temp.y<n-1 && check[temp.x][temp.y+1]==0 && map[temp.x][temp.y+1]!=1 ) {
					loca push = new loca(temp.x, temp.y+1);
					queue.offer(push); check[temp.x][temp.y+1] = check[temp.x][temp.y]+1;
				}
				if(temp.x<n-1 && check[temp.x+1][temp.y]==0 && map[temp.x+1][temp.y]!=1 ) {
					loca push = new loca(temp.x+1, temp.y);
					queue.offer(push); check[temp.x+1][temp.y] = check[temp.x][temp.y]+1;
				}
			}
			if(goal.x==-1) tf = false; // 승객을 탑승시키지 못한 경우
			if(tf==false) break;
			
			for(int arr[] : check)
				Arrays.fill(arr, 0);
			while(!queue.isEmpty()) { // 도착지 찾기
				loca temp = queue.poll();
				if(temp.x==goal.x && temp.y==goal.y) {
					if(fuel-check[temp.x][temp.y]<0) {
						tf=false; break;
					}
					fuel += check[temp.x][temp.y];
					queue.clear(); queue.offer(temp); // 큐 clear 및 현 위치 offer
					break;
				}
				if(temp.x>0 && check[temp.x-1][temp.y]==0 && map[temp.x-1][temp.y]!=1 ) {
					loca push = new loca(temp.x-1, temp.y);
					queue.offer(push); check[temp.x-1][temp.y] = check[temp.x][temp.y]+1;
				}
				if(temp.y>0 && check[temp.x][temp.y-1]==0 && map[temp.x][temp.y-1]!=1 ) {
					loca push = new loca(temp.x, temp.y-1);
					queue.offer(push); check[temp.x][temp.y-1] = check[temp.x][temp.y]+1;
				}
				if(temp.y<n-1 && check[temp.x][temp.y+1]==0 && map[temp.x][temp.y+1]!=1 ) {
					loca push = new loca(temp.x, temp.y+1);
					queue.offer(push); check[temp.x][temp.y+1] = check[temp.x][temp.y]+1;
				}
				if(temp.x<n-1 && check[temp.x+1][temp.y]==0 && map[temp.x+1][temp.y]!=1 ) {
					loca push = new loca(temp.x+1, temp.y);
					queue.offer(push); check[temp.x+1][temp.y] = check[temp.x][temp.y]+1;
				}
			}
			if(queue.isEmpty()) tf=false; // 도착지를 찾지 못한 경우
			if(tf==false) break;
		}
		if(tf==false) System.out.println("-1");
		else System.out.println(fuel);
	}
}

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

문제

문제

출처

ICPC

7%정도에서 틀리는데 반례나 조언 부탁드립니다.

bamboo_703 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말