[C++] 백준 9205번 맥주 마시면서 걸어가기

DFS, BFS 문제입니다.

현재 위치에서 도착지까지 이동할 수 있는지 확인하고,
편의점의 위치를 vector에 넣어놓고 하나씩 꺼내면서 이동이 가능한지 체크했습니다.
DFS를 이용해서 이동이 가능하다면 그 위치에서 다시 탐색합니다.

시작위치를 DFS에 넣고 1~3을 반복합니다.

DFS
1. 도착지와의 거리가 1000이하인지 - 맞다면 flag = 1 (happy)
2. 편의점 하나씩 탐색 - 이미 방문 했다면 continue;
3. 편의점과의 거리가 1000이하라면 DFS(편의점 위치)

flag == 1 이라면 happy를 출력해주고
flag == 0 이라면 sad를 출력해줍니다.

 

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

int n;
int ts;
int x, y;
int flag;
int nowX, nowY;
int endX, endY;
int visit[110];
vector<pair<int, int> > mart;

void DFS(int a, int b)
{
	int num;

	num = abs(endX - a) + abs(endY - b);

	if (flag == 1 || num <= 1000) {
		flag = 1;
		return;
	}

	for (int i = 0; i < mart.size(); ++i) {
		if (visit[i] == 1) {
			continue;
		}

		num = abs(mart[i].first - a) + abs(mart[i].second - b);

		if (num > 1000) {
			continue;
		}
		else {
			visit[i] = 1;
			DFS(mart[i].first, mart[i].second);
		}
	}
}

int main(int argc, char *argv[]) 
{
	cin >> ts;

	while (ts--) {
		cin >> n;
		cin >> nowX >> nowY;

		mart.clear();
		memset(visit, 0, sizeof(visit));

		for (int i = 0; i < n; ++i) {
			cin >> x >> y;
			mart.push_back(make_pair(x, y));
		}
		cin >> endX >> endY;

		flag = 0;
		DFS(nowX, nowY);

		if (flag == 1) {
			cout << "happy" << endl;
		}
		else {
			cout << "sad" << endl;
		}
	}
	return 0;
}