글 읽기 - 스타트택시 여러 상황 고려해봤는데 왜 틀렸는지 모르겠습니다

heejin62 3년 전 0

테스트케이스 여러개 만들어서 돌려봤는데 잘 돌아감에도 불구하고 계속 1%에서 틀리네요ㅠㅠ bfs로 최단거리에 있는 승객이랑 목적지까지의 최단거리 결정했고 다른 것들도 설명 되어있는대로 한거같은데 왜 틀리는지 모르겠네요ㅠㅠ 어떤 예외경우를 제가 생각을 안한건지 잘 모르겠습니다. 혹시 반례가 있거나 첨삭 가능하시면 부탁 드릴게요!!

아 53번째 줄에서 "'map'에서 잘못될 데이터를 읽고 있습니다"라는 warning이 뜨는데 해결을 못했어요 테케 돌리는데에는 문제가 없었기도 하고요. 혹시 그거 때문인지, 또 어떻게 고쳐야하는지도 봐주시면 감사하겠습니다!

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

struct INFO
{
	int carx, cary, fuel, used = 0;
};

int N, M;
int map[22][22], res, done;
int dX[4] = { 0,-1,1,0 }, dY[4] = { -1,0,0,1 };
pair<int, int> destination[21][21];
INFO start;

void init()
{
	cin >> N >> M >> start.fuel;
	// initialize map
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			int m;
			cin >> m;
			if (m == 1)
				map[i][j] = -1;
			else
				map[i][j] = 0;
		}
	}

	cin >> start.cary >> start.carx;
	// 승객정보 input
	for (int i = 1; i <= M; i++)
	{
		int sy, sx, dy, dx;
		cin >> sy >> sx >> dy >> dx;
		map[sy][sx] = i; // map에 승객번호 입력
		destination[sy][sx] = make_pair(dy, dx);
	}
}

void taxing(int& dy, int& dx, INFO& init) // dy & dx가 -1 경우 다음 손님 search
{							// else dy,dx로 가는 최단경로 찾기
	bool visited[21][21] = { false, };
	queue<INFO> que;
	que.push(init); // 손님 탑승 전 OR 손님 drop 후 초기상황
	while (!que.empty())
	{
		INFO curr = que.front();
		que.pop();
		if (map[curr.cary][curr.carx] > 0 && dy == -1 && dx == -1) // 손님 태우기
		{
			if (curr.fuel == 0) // 연료 0 일경우 손님 탑승 불가
			{
				continue;
			}

			// 손님 정보 얻기 (목적지)
			dy = destination[curr.cary][curr.carx].first; dx = destination[curr.cary][curr.carx].second; // 손님 목적지
			init = { curr.carx, curr.cary, curr.fuel, 0 }; // 현재 차 상태
			map[curr.cary][curr.carx] = 0; // 태운 승객 정보 map에서 없애기
			return;
		}
		if (curr.cary == dy && curr.carx == dx) // 목적지 도착시 (승객 drop)
		{
			int new_fuel = curr.fuel + curr.used * 2;
			done++;
			dy = -1; dx = -1;
			init = { curr.carx, curr.cary, new_fuel, 0 };
			return;
		}
		if (curr.fuel == 0) // 연료 0 일경우 운영 중지
		{
			continue; // 같은 거리의 블럭들 체크
		}
		for (int i = 0; i < 4; i++)
		{
			int ny = curr.cary + dY[i], nx = curr.carx + dX[i];
			if (ny > 0 && ny <= N && nx > 0 && ny <= N && !visited[ny][nx] && map[ny][nx] != -1) // 이동가능 enqueue
			{
				INFO next = { nx, ny, curr.fuel - 1, curr.used + 1 };
				visited[ny][nx] = true;
				que.push(next);
			}
		}
	}
	res = -1;
	return;
}

int main()
{
	init();
	int dy = -1, dx = -1;
	INFO curr = start;
	while (done < M)
	{
		// cout << "INIT: " << curr.cary << ", " << curr.carx << ", " << curr.fuel << ", " << curr.used << "\t" << dy << ", " << dx << endl;
		taxing(dy, dx, curr);
		// cout << "After: " << curr.cary << ", " << curr.carx << ", " << curr.fuel << ", " << curr.used << "\t" << dy << ", " << dx << endl;
		// cout << "Done: " << done << "\tres: " << res <<  "\n\n" << endl;
		if (res == -1)
			break;
	}
	if (done == M)
		res = curr.fuel;
	cout << res << endl;

	return 0;
}

conkjh032 3년 전 0

저도 테스트케이스 모두 통과했지만 1%에서 멈추는 현상을 맞았습니다.

문제는 도착지점에 손님이 있을 경우 였습니다. 저는 도착지점에는 손님이 없다고 생각하고 작성했었습니다.

제가 작성한 코드와 달라서 꼼꼼히 보지 않았지만, 문제 해결에 도움이 될 수도 있어서 글을 남깁니다.

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

문제

문제

출처

ICPC

스타트택시 여러 상황 고려해봤는데 왜 틀렸는지 모르겠습니다

heejin62 3년 전 0

conkjh032 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말