글 읽기 - (풀이방법 적었습니다.) 1%에서 틀리는 이유가 뭘까요?

melon940925 3년 전 0

1%에서 틀리지만 예외가 생각나지 않네요.. 반례 부탁드려요!

도착점이 같은 승객들이 있는 경우 확인했습니다.

벽때문에 승객을 태우지 못하는 경우 확인했습니다.

도착점이 다른 승객의 출발점이랑 같은 경우 확인했습니다.(처음 출발지점에 승객이 있는 경우도 확인)

풀이방법

1. 맵에는 각 손님의 번호를 2번부터 M+1번까지 표기하였습니다.

2. 각 손님의 목적지를 나타내는 destination배열을 만들었습니다.

- destination[손님번호].y = 도착 지점의 y좌표,

- destination[손님번호].x = 도착 지점의 x좌표

3. 손님을 태우러가는 BFS를 만들었습니다.

- 손님을 태우는 BFS는 1보다 큰 번호를 만났을 때 손님을 자료구조에 담습니다.

- 손님을 만나면 BFS가 끝나고 자료구조에 담긴 손님들 중에 조건에 맞는 손님을 태웁니다.

- 손님을 태우러 가는동안 이동한 거리를 반환합니다.

- 만약 queue가 비어있을 때까지 BFS가 끝나지 않았다면 98765432를 반환합니다.

4. 손님을 도착지점까지 데려다주는 BFS를 만듭니다.

- 도착지점의 y와 x를 인자로 받고 그 지점에 도달하면 BFS가 끝나며 이동거리를 반환하는 BFS입니다.

- 만약 queue가 비어있을 때까지 BFS가 끝나지 않았다면 98765432를 반환합니다.

5. 손님을 태우러 갈때는 BFS에서 반환한 값을 연료에서 빼고 그 값이 0보다 크다면 -1을 출력 후 return 합니다.

6. 손님을 태우고 이동할 때는 BFS에서 반환한 값과 연료를 비교하여 연료가 크거나 같다면 연료+=반환값; 그렇지않다면 -1을 출력 후 return합니다.

이런식으로 만들었고, 테스트케이스도 여러가지 만들어서 동작해보았지만 오류가 없는 것 같은데, 1%에서 틀렸다고 나오네요

고수분들 도움좀 부탁드려요~

#include <bits/stdc++.h>
#define F(i,n) for(int i=1; i<=n; i++)
using namespace std;
int N, M, fuel;
inline bool det(int y, int x) {
	return (y >= 1 && y <= N && x >= 1 && x <= N);
}

struct info {
	int y, x;
	bool operator<(const info & a)const {
		if (y == a.y)return x > a.x;
		return y > a.y;
	}
};
info destination[401];
int arr[25][25];
int check[25][25];
info texi;

queue<info> q;
priority_queue<info> pq;
int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,1,-1 };
int BFS_findcustomer() {
	int y, x, ny, nx;
	int time = 0;
	while (!q.empty()) {
		int Q = q.size();
		time++;
		F(k, Q) {
			y = q.front().y; x = q.front().x;
			q.pop();
			for (int i = 0; i < 4; i++) {
				ny = y + dy[i]; nx = x + dx[i];
				if (det(ny, nx)) {
					if (!check[ny][nx]) {
						check[ny][nx] = 1;
						if (arr[ny][nx] == 1) {
							continue;
						}
						if (arr[ny][nx] > 1) {
							pq.push({ ny,nx });
						}
						q.push({ ny,nx });
					}
				}
			}
		}
		if (!pq.empty()) {
			while (!q.empty())q.pop();
			return time;
		}
	}
	return 98765432;
}

int BFS_finddestination(int Y,int X) {
	int y, x, ny, nx;
	int time = 0;
	while (!q.empty()) {
		int Q = q.size();
		time++;
		F(k, Q) {
			y = q.front().y; x = q.front().x;
			q.pop();
			for (int i = 0; i < 4; i++) {
				ny = y + dy[i]; nx = x + dx[i];
				if (det(ny, nx)) {
					if (!check[ny][nx]) {
						check[ny][nx] = 1;
						if (arr[ny][nx] == 1) {
							continue;
						}
						if (ny==Y&&nx==X) {
							while (!q.empty())q.pop();
							return time;
						}
						q.push({ ny,nx });
					}
				}
			}
		}

	}
	return 98765432;
}

int main() {
	int customNum = 2;
	int a, b;
	cin >> N >> M >> fuel;
	F(i, N)F(j, N)cin >> arr[i][j];
	cin >> a >> b;
	texi.y = a, texi.x = b;
	F(i, M) {
		cin >> a >> b;
		arr[a][b] = customNum;
		cin >> a >> b;
		destination[customNum++] = { a,b };
	}

	while (M--) {
		//cout << endl;
		//F(i, N) { cout << endl; F(j, N) { cout << arr[i][j] << ' '; } }

		info dest;
		int D;
		if (arr[texi.y][texi.x] > 1) {
			dest = destination[arr[texi.y][texi.x]];
			arr[texi.y][texi.x] = 0;
		}

		else {
			q.push({ texi.y,texi.x });
			int D = BFS_findcustomer();
			fuel -= D;
			if (fuel < 0) {
				cout << -1 << endl;
				return 0;
			}
			texi.y = pq.top().y; texi.x = pq.top().x;
			int NUM = arr[texi.y][texi.x];
			arr[texi.y][texi.x] = 0;
			dest = destination[NUM];
			memset(check, 0, sizeof(check));
			while (!pq.empty())pq.pop();
		}

		//cout << "승객을 태우고 남은 fuel: " << fuel << endl;
		//cout << "현재 택시기사의 위치 : " << texi.y << "," << texi.x << endl;
		//cout << "목표지점의 위치: " << dest.y << ',' << dest.x << endl;

		q.push({ texi.y,texi.x });
		D = BFS_finddestination(dest.y, dest.x);
		texi.y = dest.y; texi.x = dest.x;
		memset(check, 0, sizeof(check));
		if (fuel < D) {
			cout << -1 << endl;
			return 0;
		}
		fuel += D;

		//cout << "승객을 도착점에 데려다 주고 남은 fuel: " << fuel << endl;
	}
	//cout << endl;
	//F(i, N) { cout << endl; F(j, N) { cout << arr[i][j] << ' '; } }

	cout << fuel << endl;
}

zxcv5052 3년 전 1

최단거리가 가장 짧은 승객을 고른다. 그런 승객이 여러 명이면 그중 행 번호가 가장 작은 승객을, 그런 승객도 여러 명이면 그중 열 번호가 가장 작은 승객을 고른다.

이 부분 조건 적용하신건가요?

melon940925 3년 전 0

네! 우선순위큐를 사용하였습니다

whgusdn321 1년 전 1

지금은 맞으셨네요

melon940925 1년 전 0

아 네.. 어쩌다보니 맞았는데 왜 맞게 됐는지 기억은 잘 안나네요.

해결 됨으로 바꿨습니다.

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

문제

문제

출처

ICPC

(풀이방법 적었습니다.) 1%에서 틀리는 이유가 뭘까요?

melon940925 3년 전 0

zxcv5052 3년 전 1

melon940925 3년 전 0

whgusdn321 1년 전 1

melon940925 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말