백준 9205 : 맥주마시면서 걸어가기 c++

www.acmicpc.net/problem/9205

9205번: 맥주 마시면서 걸어가기

문제 풀이

1. 무사히 도착하면 flag를 1로 하여 happy 출력

2. 시작지부터 dfs 시작

 

DFS

1) 지금 위치랑 목적지랑 거리가 1000이하면 flag =1 하고 종료

2)  for문으로 market들 확인, 방문한거면 재낀다

3) 방문안했어도 거리가 1000넘으면 못가니까 재낀다

4) 방문 가능한 market으로 이동 후 DFS

 

 

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

pair<int, int> house;
pair<int, int> festival;
vector<pair<int, int> > market;
int visited[101] = { 0, };
int flag;

void dfs(int x, int y)
{
	if (abs(x - festival.first) + abs(y - festival.second) <= 1000) // 최대 이동거리는 20 * 50 =1000
	{
		flag = 1;
		return;
	}

	for (int i = 0; i < market.size(); i++)
	{
		if (visited[i] == 1) // 방문한거 재껴
			continue;

		if (abs(x - market[i].first) + abs(y - market[i].second) > 1000) //갈수 없는곳 재껴
			continue;
		
		visited[i] = 1;
		dfs(market[i].first, market[i].second);
	}
}


int main()
{
	int tc;
	int n;
	int data_1, data_2;
	cin >> tc;
	for (int i = 0; i < tc; i++)
	{
		for (int j = 0; j < 101; j++)
			visited[j] = 0;

		flag = 0;
		while (!market.empty())
			market.pop_back();
		cin >> n;
		cin >> data_1 >> data_2;
		house.first = data_1;
		house.second = data_2;


		for (int j = 0; j < n; j++)
		{
			cin >> data_1 >> data_2;
			market.push_back(make_pair(data_1, data_2));
		}

		cin >> data_1 >> data_2;
		festival.first = data_1;
		festival.second = data_2;

		dfs(house.first, house.second);

		if (flag == 1)
			cout << "happy" << endl;
		else
			cout << "sad" << endl;

	}
	return 0;
}

 

 

 

후기

 음... 솔직히 말해서 왜 풀리는지 모르겠다, 그냥 완전 직관적으로 떠오르는대로 해버렸는데 맞아버렸다

내가 의문인건 만약에 주어진 market들이 점점 목적지랑 멀어지는 곳에 있는 거라면...?

 

의문 해결!!

 

시작지에서 목적지가 1000이하던지!!

그 어떤 편의점 하나라도 목적지까지 1000이하면 되니까 노상관!!!