글 읽기 - 혹시 어디서 틀렸는지 알수있을까요 ?

eodlsgh123 3년 전 0

2개의 함수를 사용해서 풀고 있으며

함수 (getStart) 는 현재 택시의 위치로 부터 승객의 위치, 남은 연료, 찾은 승객 번호 정보를 담은 Node 를 반환합니다.

함수 (getEnd) 는 현재 승객의 위치로 부터 목적지의 위치, 남은 연료, 이동한 횟수를 담은 Node를 반환합니다.

for문을 사용하여 승객의 횟수만큼 반복하며 가장 초기 node now에 시작 위치 좌표, 연료를 넣고

getStart 함수를 사용해서 승객의 위치정보와 승객 번호, 잔여 연료 를 담은 Node를 반환 시켜 해당 노드의

잔여 연료값이 0보다 작거나 같다면 res 변수에 -1을 넣고 for문을 종료합니다.

만약 잔여 연료가 0보다 큰경우라면 getEnd 함수를 통해 목적지 좌표, 남은 연료, 이동횟수를 담은 노드를 반환시킵니다.

만약 해당 반환 된 노드의 잔여 연료량이 0보다 크거나 같다면 연료를 잔여 연료 + 이동횟수 * 2 값을 시켜줘 갱신합니다.

그리고 다시 위의 getStart 함수의 매개변수로 연료값을 갱신한 노드를 넣어줍니다.

위와 같은 과정을 반복하며 문제를 해결하고 있는데 1 % 에서 바로 틀리게 나오는데 어디가 문제일까요 ?

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>

using namespace std;
struct endNode{
	int y, x;
};
struct Node{
	int y, x;
	int num;
	int energy;
	int cnt;
};
// 각 승객의번호에 해당하는 인덱스에 해당 승객의 목적지 좌표가 들어있음
endNode endList[401];
vector<Node> vect;

int checkY[4] = { +1, -1, 0, 0, };
int checkX[4] = { 0, 0, +1, -1 };

// 벽의 위치
int map[20][20];
// 승객의 위치
int startMap[20][20];

int k, n, m;

bool comps(Node a, Node b){
	if (a.y < b.y) return true;
	if (a.y > b.y) return false;
	if (a.y == b.y){
		if (a.x < b.x) return true;
		else{
			return false;
		}
	}
}

int getStart(Node nodes){
	// 현재 택시의 위치가 승객의 위치와 동일하다면 1반환
	if (startMap[nodes.y][nodes.x] > 0){
		vect.push_back({ nodes.y, nodes.x, startMap[nodes.y][nodes.x], nodes.energy, 0 });
		return 1;
	}

	int visit[20][20] = {0};
	visit[nodes.y][nodes.x] = 1;
	queue<Node> qu;
	qu.push(nodes);

	int flag = 0;
	while (!qu.empty()){
		Node now = qu.front();

		for (int i = 0; i < 4; ++i){
			int dy = now.y + checkY[i];
			int dx = now.x + checkX[i];
			if (dy < 0 || dx < 0 || dy >= n || dx >= n) continue;
			if (visit[dy][dx] == 1) continue;
			if (map[dy][dx] == 1) continue;

			// 승객을 1명도 찾지 못했을시 qu에 push
			if (flag == 0 && startMap[dy][dx] == 0){
				visit[dy][dx] = 1;
				qu.push({ dy, dx, 0, now.energy - 1, 0 });
			}

			// 승객을 한명이라고 찾았다면 해당 시점부터 더이상 qu에 push하지 않으며
			// 같은 위치의 승객까지 탐색
			if (startMap[dy][dx] > 0){
				flag = 1;
				visit[dy][dx] = 1;
				int num = startMap[dy][dx];
				vect.push_back({ dy, dx, num, now.energy - 1, 0 });
			}
		}
		qu.pop();
	}
	// 만약 승객을 한명도 못 찾았다면 -1 반환
	if (vect.empty()) return -1;
	else return 1;
}

// 승객 위치로 부터 목적지 탐색
int getEnd(Node nodes){
	int visit[20][20] = { 0 };
	visit[nodes.y][nodes.x] = 1;
	queue<Node> qu;
	qu.push(nodes);

	while (!qu.empty()){
		Node now = qu.front();
		for (int i = 0; i < 4; ++i){
			int dy = now.y + checkY[i];
			int dx = now.x + checkX[i];

			if (dy < 0 || dx < 0 || dy >= n || dx >= n) continue;
			if (map[dy][dx] == 1) continue;
			if (visit[dy][dx] == 1) continue;

			// 만약 목적지일 경우
			if (dy == endList[now.num].y && dx == endList[now.num].x){
				// 목적지에 도착했을 때 남은 연료가 0보다 크거나 같다면 1 반환
				if (now.energy - 1 >= 0){
					vect.push_back({ dy, dx, 0, now.energy - 1, now.cnt + 1 });
					return 1;
				}
				// 목적지에 도착했을 때 남은 연료가 0보다 작다면 0반환
				else{
					return 0;
				}
			}

			else{
				visit[dy][dx] = 1;
				qu.push({ dy, dx, now.num, now.energy - 1, now.cnt + 1 });
			}
		}
		qu.pop();
	}
	return 0;
}




int main(){
	//freopen_s(new FILE*, "tes.text", "r", stdin);
	cin >> n >> m >> k;
	int sy, sx;
	int res;
	for (int i = 0; i < n; ++i){
		for (int j = 0; j < n; ++j){
			cin >> map[i][j];
		}
	}
	cin >> sy >> sx;
	for (int i = 1; i <= m; ++i){
		int y, x, ey, ex;
		cin >> y >> x >> ey >> ex;
		startMap[y- 1][x -1] = i;
		endList[i] = { ey- 1, ex -1 };
	}
	Node now = { sy -1, sx-1, 0, k, 0 };

	// 승객 수 만큼 반복
	for (int i = 1; i <= m; ++i){
		// 만약 승객을 한명도 못 찾았다면 res = -1
		if (getStart(now) == -1){ res = -1; break; }

		sort(vect.begin(), vect.end(), comps);
		now = vect.front();
		vect.clear();
		// 승객을 찾았지만 연료가 0보다 작거나 같다면 res = -1
		if (now.energy <= 0){ res = -1; break; }

		// 만약 승객을 찾았으면서 연료가 0보다 크다면
		else{
            // 승객을 찾았기 때문에 승객의 위치는 0으로 초기화
			startMap[now.y][now.x] = 0;
			// 목적지에 도착했을 때 연료가 (0 또는 0 보다 클때) 남아있다면 
			// 에너지 충전, 이동횟수 초기화
			if (getEnd(now) == 1){
				now = vect.front();
				vect.clear();
				now.energy += now.cnt * 2;
				now.cnt = 0;
			}
			// 목적지 도착시 연료가 0보다 작다면 res = -1
			else{
				res = -1;
				break;
			}
		}
		// 남은 연료 res에 갱신
		res = now.energy;
	}

	cout << res << endl;
}

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

문제

문제

출처

ICPC

혹시 어디서 틀렸는지 알수있을까요 ?

eodlsgh123 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말