글 읽기 - 문제에서 제 코드가 어느 부분이 잘못 되었는지 전혀 모르겠습니다.

kimmoon4 3년 전 0

해당문제를 아래 방법순으로 풀었습니다

1. map, smap(출발 점들을 기록한 map) 을 입력받고 승객들의 시작점과 도착점들을 입력받는다.

2. take를 통해 몇번째 승객을 태워야하는 인덱스를 반환하는데 priority queue를 활용하여 pq의 top을 반환 하지만 만약 pq가 비어있을경우(벽에 가로막혀 어느 승객도 못태울 경우)에는 -1을 반환하여 종료 하도록 합니다.

3. bfs함수를 통해 최단거리를 방문하는데 가는데 소모한 연료를 체크하여 남아있는 연료보다 작거나 같을 경우에만 원래 연료에서 사용해야할 연료를 더해준후 true를 반환합니다. 이외의 경우에는 false를 반환합니다

4. 총 m 번을 반복하고 끝날경우에는 남은 연료를 출력합니다.

위 순서대로 풀었는데 바로 틀렸습니다가 나옵니다. 고수님들 제발 도와주십쇼....

#include <iostream>
#include <vector>
#include <queue>
#include <deque>
#include <algorithm>
#include <cstring>
#include <functional>
using namespace std;

pair<int, int> dir[] = { {-1,0},{0,-1},{0,1},{1,0} };

int n, m, f;
int map[21][21];
int smap[21][21];
pair<int, int> taxi;
bool check[21 * 21];
bool visit[21][21];
vector<pair<int, int>> start;
vector<pair<int, int>> finish;

int take(int y, int x)
{
	memset(visit, 0, sizeof(visit));
	visit[y][x] = true;
	queue<pair<pair<int, int>, int>> q;
	priority_queue<pair<int, pair<int, pair<int, int>>>, vector<pair<int, pair<int, pair<int, int>>>>, greater<pair<int, pair<int, pair<int, int>>>>> pq;
	q.push({ { y,x },0 });
	if (smap[y][x] != 0&&!check[smap[y][x]-1])
	{
		check[smap[y][x] - 1];
		return smap[y][x] - 1;
	}
	while (!q.empty())
	{
		int cy = q.front().first.first;
		int cx = q.front().first.second;
		int fuel = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++)
		{
			int ny = cy + dir[i].first;
			int nx = cx + dir[i].second;
			int nf = fuel + 1;
			if (1 <= nx && nx <= n && 1 <= ny && ny <= n && !visit[ny][nx] && smap[ny][nx] != -1)
			{
				if (smap[ny][nx] != 0 && !check[smap[ny][nx] - 1])
				{
					pq.push({ nf,{ny,{nx,smap[ny][nx]-1}} });
				}
				visit[ny][nx] = true;
				q.push({ { ny,nx },fuel + 1 });
			}
		}
	}
	if (pq.empty())
		return -1;
	f -= pq.top().first;
	check[pq.top().second.second.second] = true;
	return pq.top().second.second.second;
}

bool bfs(int idx)
{
	memset(visit, 0, sizeof(visit));
	auto s = start[idx];
	auto e = finish[idx];
	visit[s.first][s.second] = true;
	queue<pair<pair<int, int>, int>> q;
	q.push({ { s.first,s.second },0 });
	while (!q.empty())
	{
		int cy = q.front().first.first;
		int cx = q.front().first.second;
		int fuel = q.front().second;
		q.pop();
		if (make_pair(cy, cx) == e)
		{
			if (fuel > f)
				return false;
			else
			{
				taxi = { cy,cx };
				f += fuel;
				return true;
			}
		}
		for (int i = 0; i < 4; i++)
		{
			int ny = cy + dir[i].first;
			int nx = cx + dir[i].second;
			int nf = fuel + 1;
			if (1 <= nx && nx <= n && 1 <= ny && ny <= n && !visit[ny][nx] && map[ny][nx] != 1)
			{
				if (make_pair(ny, nx) == e)
				{
					if (nf > f)
						return false;
					else
					{
						taxi = { ny,nx };
						f += nf;
						return true;
					}
				}
				visit[ny][nx] = true;
				q.push({ {ny,nx} , nf });
			}
		}
	}
	return false;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m >> f;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
		{
			cin >> map[i][j];
			if (map[i][j] == 1)
				smap[i][j] = -1;
		}
	cin >> taxi.first >> taxi.second;
	for (int i = 0; i < m; i++)
	{
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		smap[a][b] = i + 1;
		start.push_back({ a,b });
		finish.push_back({ c,d });
	}
	while (f != 0)
	{
		int idx = take(taxi.first, taxi.second);
		bool e = true;
		if (idx == -1)
		{
			cout << -1 << '\n';
			return 0;
		}
		if (f <= 0)
		{
			cout << -1 << '\n';
			return 0;
		}
		if (!bfs(idx))
		{
			cout << -1 << '\n';
			return 0;
		}
		if (--m == 0)
			break;
	}
	cout << f << '\n';
}

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

문제

문제

출처

ICPC

문제에서 제 코드가 어느 부분이 잘못 되었는지 전혀 모르겠습니다.

kimmoon4 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말