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

각 정점마다 갈 수 있는 정점을 연결하여 그래프를 이용하여 문제를 풀었다. 연결을 한 그래프를 가지고 dfs를 적용하여 페스티벌 좌표에 도착하면 1을 리턴하여 happy를 출력하고 0을 리턴하면 sad를 출력하도록 구현했다.

 

 

visited는 해당 정점을 방문 여부를 판별하고 adj 2차원 벡터는 어느 정점끼리 연결되어 있는지 저장한 벡터다. adj[2]에 { 0, 1 }이 있으면 2번 정점은 0번 정점, 1번 정점과 연결되어 해당 정점으로 갈 수 있다는 뜻이다.

 

 

테스트케이스를 시작할 때 각 배열들을 초기화한 후 n+2개의 정점들을 입력한다. 입력 후 각 정점들간의 거리를 계산하여 맨해튼 거리가 1000보다 작거나 같을 경우 i번째에서 j번째로 갈 수 있다는 뜻이므로 adj 배열에 추가한다.

 

 

0번째 정점을 방문 표시를 해주고 0번째 정점을 시작으로 dfs를 시작한다.

 

 

depth는 현재 정점의 위치를 뜻하고 depth == n+1이면 목적지에 도달했다는 뜻이므로 1을 리턴한다. 아직 목적지에 도착하지 않았을 경우 해당 정점과 연결된 정점들을 반복문을 통해 방문한다.

 

 

전체 코드

#include <bits/stdc++.h>

using namespace std;

vector<bool> visited(105, false); // 방문 표시
vector<vector<int>> adj(105, vector<int>()); // 인접한 spot 표시 -> adj[i]에 { 0,2,3 } 이 있으면 spot[i]는 spot[0], spot[2], spot[3] 으로 갈 수 있다는 뜻
int t, n;

int func(int depth) {
	// n+1번째 spot(목적지)에 도달
	if (depth == n + 1)
		return 1;

	// 현재 spot으로부터 연결된 spot 방문
	for (auto i : adj[depth]) {
		if (!visited[i]) {
			visited[i] = true;
			if (func(i))
				return 1;
		}
	}

	return 0;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> t;

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

		// 배열 초기화
		fill(visited.begin(), visited.end(), false);
		for (int i = 0; i < 105; i++)
			adj[i].clear();
		vector<pair<int, int>> spot(105);

		for (int i = 0; i < n + 2; i++) 
			cin >> spot[i].first >> spot[i].second;

		// 맥주가 바닥 나지 않고 갈 수 있는 경우 체크
		for (int i = 0; i < n + 2; i++) {
			for (int j = i + 1; j < n + 2; j++) {
				if (abs(spot[i].first - spot[j].first) + abs(spot[i].second - spot[j].second) <= 1000) {
					adj[i].push_back(j);
					adj[j].push_back(i);
				}
			}
		}
		
		visited[0] = true;
		if (func(0))
			cout << "happy\n";
		else
			cout << "sad\n";
	}

	return 0;
}