백준 / BOJ / 9205 맥주 마시면서 걸어가기 C++

www.acmicpc.net/problem/9205

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

날은 춥지만 요즘 같은 코로나 시대에 밖에서 맥주를 먹고 싶어 골라본 문제입니다.

여담으로 본가에는 12/2 10시 기준으로 경남 전체에 7명이 나왔네요. 물론 지금 전세계 어디든 안 위험한 곳이 없지만 서울이 193명인것에 비해 아주 적은 수치라 부럽기도 합니다. 좁은 고시원 같은 방에서 몇 달을 보내는 건지....

조금 더 여담을 말하면 여름에 본가에 내려갔더니 저를 경계하여 너무 슬펐습니다. 집이랑 학교만 왔다갔다 하는데 정말 슬프네요 ㅠㅜㅠㅜ 심지어 알바하는 곳도 학교 안에 있습니다.... 겨울 쯤 코로나 환자가 급증할 것이란 예상과 맞게 얼마전부터 급증 중이네요 하루 빨리 우리 모두 자유롭게 돌아다닐 수 있는 날이 오면 좋겠습니다.

 

여담을 마무리하고 문제 풀이를 진행하겠습니다. 

최단 거리 등을 구하는 것이 아닌 도착 유무만 물었기 때문에 dfs를 이용하여 풀었고 집, 편의점, 목적지의 좌표를 노드라 생각하고 풀면 됩니다. 해당 노드에서 다른 노드까지의 거리가 1000 (맨해튼 거리) 이하이면 그 곳까지 도착할 수 있습니다. 그렇게 모든 노드를 dfs를 이용하여 탐색하고, 마지막 n+1번째 노드의 check값이 true이면 목적지에 도달, 그렇지 않으면 실패한 것입니다.

 

코드는 다음과 같습니다.

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int t, n;
vector<int>graph[102]; //출발, 도착 포함
bool check[102];
vector<pair<int, int>>location;

int dist(pair<int, int>p, pair<int, int>q)
{
	int dx = abs(p.second - q.second);
	int dy = abs(p.first - q.first);
	return dx + dy;
}

void dfs(int idx)
{
	check[idx] = true;

	for (int i = 0; i < graph[idx].size(); i++)
	{
		int next = graph[idx][i];
		if (!check[next])
			dfs(next);
	}
}

void init_and_start()
{
	for (int i = 0; i < 102; i++)
	{
		graph[i].clear();
		check[i] = false;
	}
	location.clear();

	cin >> n;
	int s1, s2; //시작점
	cin >> s1 >> s2;
	location.push_back({ s2,s1 });
	for (int i = 0; i < n; i++) {
		int y, x;
		cin >> x >> y;
		location.push_back({ y,x });
	}
	int e1, e2; //끝점
	cin >> e1 >> e2;
	location.push_back({ e2,e1 });
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> t;
	while (t--)
	{
		init_and_start();

		//가능한 노드 넣기
		for (int i = 0; i < location.size(); i++)
		{
			for (int j = i + 1; j < location.size(); j++)
			{
				pair<int, int>p1 = location[i];
				pair<int, int>p2 = location[j];
				if (dist(p1, p2) <= 1000) 
				{
					graph[i].push_back(j);
					graph[j].push_back(i);
				}
			}
		}

		//처음은 0번째 노드, 마지막은 n+1번Š 노드
		dfs(0);

		if (check[n + 1])
			cout << "happy" << '\n';
		else
			cout << "sad" << '\n';
	}
}