글 읽기 - 9205 질문 입니다!

byunghoonpark 5년 전 0

현재 좌표에서 목표지점까지 갈 수 있는지
갈 수 없다면 가장 가까운 편의점까지 갈 수 있는지
마지막 편의점일 때 목표지점까지 갈 수 있는지

이렇게 생각했는데 틀렸다고 나오네요. 힌트 주시면 감사하겠습니다!

#include <iostream>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;

struct POS {
	int x, y, dis;
};

int homex, homey;
int targetx, targety;
bool flag;
int n;

int func(int homex,int homey, int posx, int posy) {
	return abs(homex - posx) + abs(homey - posy);
}

bool operator<(POS p1, POS p2) {
	return (p1.dis > p2.dis);
}

priority_queue<POS> pq[1];

void dfs(int nowx, int nowy, int index) { // index는 편의점 갯수 

	if (index == n) { // 남은 편의점 없을 때
		if ( func(nowx, nowy, targetx, targety) / 50 > 20) {
			flag = false;
			return;
		}
		
		flag = true;
		return;
		
	}

	else {

		if ( func(nowx, nowy, targetx, targety) / 50 <= 20) {  // 현재 위치에서 갈 수 있으면
			flag = true;
			return;
		}

		else { // 현재 위치에서 갈 수 없을 때

			POS cur_pos = pq[0].top();
			pq[0].pop();
			
			int tmp = func(nowx, nowy, cur_pos.x, cur_pos.y);
			if (tmp / 50 > 20) { // 가장 가까운 편의점도 못가면
				flag = false;
				return;
			}

			else // 가장 가까운 편의점으로 갈 수 있으면 
				return dfs(cur_pos.x, cur_pos.y, index + 1);
		}
	}
	
	
}

int main(void) {
	int testcases;
	scanf("%d", &testcases);
	while (testcases--) {

		vector<POS> v;
		POS pos;
		flag = false;
		scanf("%d", &n);

		for (int i = 0; i < n + 2; i++) {
			if (i == 0) 
				scanf("%d %d", &homex, &homey);
			else if (i == n + 1) 
				scanf("%d %d", &targetx, &targety);
			else {
				scanf("%d %d", &pos.x, &pos.y);
				pos.dis = func(homex, homey, pos.x, pos.y);
				pq[0].push(pos);
			}
		}

		dfs(homex,homey,0);
		
		if (flag)
			cout << "happy" << '\n';
		else
			cout << "sad" << '\n';
	}
	return 0;
}

ekwoo 5년 전 0

굳이 가장 가까운 편의점에 갈 필요 없고

BFS돌려서 구하면 바로 나올 것 같은데요;;

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

문제

문제

출처

ICPC

9205 질문 입니다!

byunghoonpark 5년 전 0

ekwoo 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말