글 읽기 - 87%에서 '틀렸습니다' 도와주세요 고수님들!!!!!

cw20 3년 전 4

87%에서 "틀렸습니다."라고 뜹니다..

아무리 생각해봐도 어떤 것이 잘못되었는지 모르겠습니다.

일단 저는 승객의 시작점과 도착점 사이의 거리를 미리 구해 놓았습니다.

도착점에 도착할 수 없는 경우 택시를 이동시키지 않고 바로 종료 시켰습니다.

이런 경우가 없다면,

택시를 이동 시키면서 가장 가까운 승객을 찾았습니다.

이 때, 연료가 바닥나면 이동을 멈추고 종료되게 하였습니다...

제가 어떤 것을 놓치고 있는 것 일까요?

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

struct Pos{
	int x, y;
}; // 좌표 정보 담을 구조체

struct Passenger{
	Pos start, end;
	int dist = 0;
	
}; // 승객의 정보를 담을 구조체

int getDist(int N, int **road, Pos start, Pos end);

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	
	int N, M, fuel;
	cin >> N >> M >> fuel;
	
	int **road = new int*[N]; // 지도(길) 정보
	for(int i = 0; i < N; i++){
		road[i] = new int[N];
		for(int j = 0; j < N; j++){
			cin >> road[i][j];
		}
	}
	
	Pos taxi; // 택시의 위치
	cin >> taxi.x >> taxi.y;
	taxi.x--;
	taxi.y--;
	
	Passenger *passenger = new Passenger[M+2]; // 승객의 위치 담을 배열
	for(int i = 2; i < M+2; i++){
		int x, y;
		
		cin >> x >> y;
		passenger[i].start.x = x-1;
		passenger[i].start.y = y-1;
		road[x-1][y-1] = i;
		
		cin >> x >> y;
		passenger[i].end.x = x-1;
		passenger[i].end.y = y-1;
		
		// 승객의 출발 및 도착 간의 거리 구함
		passenger[i].dist = getDist(N,road,passenger[i].start,passenger[i].end);
		
		if(passenger[i].dist < 0){
			cout << -1;
			return 0;
		}
	}
	
	int dir[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
	while(M--){
		bool **visit = new bool*[N];
		for(int i = 0; i < N; i++){
			visit[i] = new bool[N];
			memset(visit[i],false,N);
		}
		
		queue<Pos> q;
		q.push(taxi);
		visit[taxi.x][taxi.y] = true;
		
		int dist = 0;
		while(!q.empty()){
			int min_x = N, min_y = N; // 같은 거리에 있는 승객 중 행이 작고 열이 작은 위치에 있는 승객에게 우선순위를 주기 위함
			
			int q_size = q.size();
			for(int s = 0; s < q_size; s++){
				int x = q.front().x;
				int y = q.front().y;
				q.pop();
				
				if(road[x][y] > 1){ // 승객이 있는 경우
					if(x < min_x){
						min_x = x;
						min_y = y;
					}
					else if(x == min_x){
						if(y < min_y){
							min_y = y;
						}
					}
					continue;
				}
				
				for(int d = 0; d < 4; d++){
					int dx = x+dir[d][0], dy = y+dir[d][1];
					if(dx >= 0 && dx < N && dy >= 0 && dy < N){
						if(!visit[dx][dy] && road[dx][dy] != 1){
							q.push({dx,dy});
							visit[dx][dy] = true;
						}
					}
				}
			}
			
			if(min_x != N && min_y != N){ // 승객을 찾은 경우
				int num = road[min_x][min_y];
				road[min_x][min_y] = 0;
				taxi.x = passenger[num].end.x;
				taxi.y = passenger[num].end.y;
				fuel -= dist;
				fuel -= passenger[num].dist; // 이동 거리만큼 연료 감소
				
				if(fuel < 0){ // 연료가 0보다 작다면(도착한 순간 0이 되는 경우에는 연료가 추가될 것이므로 이 경우에 포함되지 않음)
					fuel = -1; // 연료를 -1로 바꾸기(출력을 위해)
				}
				else{ // 연료가 남아있다면
					fuel += 2*passenger[num].dist; // 이동한 거리 2배만큼 연료 더해 줌
				}
				break;
			}
			
			dist++;
		}
		
		if(fuel < 0){ // 남은 연료 없다면
			break; // 영업 종료
		}
	}
	
	cout << fuel;
	
	return 0;
}

int getDist(int N, int **road, Pos start, Pos end){
	bool **visit = new bool*[N];
	for(int i = 0; i < N; i++){
		visit[i] = new bool[N];
		memset(visit[i],false,N);
	}
	
	queue<Pos> q;
	q.push(start);
	
	int dist = 0;
	int dir[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
	while(!q.empty()){
		int q_size = q.size();
		for(int s = 0; s < q_size; s++){
			int x = q.front().x;
			int y = q.front().y;
			
			if(x == end.x && y == end.y){
				return dist;
			}
			
			q.pop();
			
			for(int d = 0; d < 4; d++){
				int dx = x+dir[d][0], dy = y+dir[d][1];
				if(dx >= 0 && dx < N && dy >= 0 && dy < N){
					if(!visit[dx][dy] && road[dx][dy] != 1){
						q.push({dx,dy});
						visit[dx][dy] = true;
					}
				}
			}
		}
		dist++;
	}
	
	return -1;
}

tdm1223 3년 전 6

저도 87%에서 막혔었는데 택시에서 가장 가까운 거리에 있는 손님이 없을 경우를 수정하니 해결되었습니다.

제가 해결할때 사용한 테스트 케이스입니다.

3 1 100

0 1 0

1 1

1 3 3 3

ans : -1

cw20 3년 전 0

감사합니다!! 드디어 해결할 수 있게 되었습니다ㅠㅠ

wwwbklee 2년 전 0

감사합니다. 축복받으실거에요

legowww 1년 전 0

고마워요~

rego0723 1년 전 0

감사합니다 감사합니다 감사합니다

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

문제

문제

출처

ICPC

87%에서 '틀렸습니다' 도와주세요 고수님들!!!!!

cw20 3년 전 4

tdm1223 3년 전 6

cw20 3년 전 0

wwwbklee 2년 전 0

legowww 1년 전 0

rego0723 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말