문제

https://www.acmicpc.net/problem/9205

---

풀이

틀린 풀이

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility> 
#include <cstring> 
#include <queue> 
#include <cmath> 
using namespace std;
typedef pair<int, int> pii; 

int n; 
vector<pii> v; 

void input(){
	cin >> n; 

	for(int i = 0; i < n + 2; i++){
		int x, y; 
		cin >> x >> y; 
		v.push_back({x, y}); 
	}
}

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

	int t; 
	cin >> t; 

	while(t--){
		input();

		bool fail = false; 
		for(int i = 0; i < n + 1; i++){
			int dx = abs(v[i].first - v[i + 1].first);
			int dy = abs(v[i].second - v[i + 1].second); 
			int dist = dx + dy;
			
			if(dist / 50 > 20){ 
				fail = true; 
				cout << "sad\n"; 
				break; 
			}
		}

		if(!fail) cout << "happy\n"; 

		v.clear(); 
	}
	
    return 0;
}

단순 무식하게,, 인접한 두 지점 사이의 거리를 20병의 맥주로 갈 수 있으면 happy, 아니면 sad를 출력하게 했더니 틀렸다.

답안

이 문제의 핵심은 주어진 조건에 따라 그래프를 직접 만드는 것이라고 생각한다. 그래프 탐색의 아주 기초적인 문제에서는 정점 간의 연결 관계가 문제에 그대로 주어진다. 하지만, 이 문제에서는 50미터마다 맥주를 1병씩 마시더라도 거리가 1000이내여서 20병으로 부족하지 않은 두 지점을 찾아서 우리가 연결시켜줘야 한다.

// 핵심 코드 

for(int i = 0; i < n + 2; i++){ 
	for(int j = i + 1; j < n + 2; j++){ 
		// 거리가 1000이내인 지점들만 연결 
		if(dist(coord[i], coord[j]) <= 50 * 20){
        	// 양방향 연결 
			graph[i].push_back(j); 
			graph[j].push_back(i); 
		}
	}
}

이렇게 정점 간의 연결 관계가 완성되면, DFS 또는 BFS로 출발점 (0)에서 도착점 (n + 1)까지 도달할 수 있는지 확인해주면 된다. 최단 거리가 아니더라도 도착점까지 도달할 수 있는지만 확인하면 되기 때문에 DFS도 사용 가능하다.

그리고 각 테스트 케이스마다 coord, graph, visited 배열의 데이터를 초기화 시키는 것도 잊지 말아야 한다!

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility> 
#include <cstring> 
#include <queue> 
#include <cmath> 
#define MAX 103 
using namespace std;
typedef pair<int, int> pii; 

int n; // 편의점 개수 
vector<pii> coord; // 출발점, 도착점, 편의점의 좌표 
vector<int> graph[MAX]; // 맨해튼 거리가 1000 이내인 좌표들끼리만 연결한 그래프 
bool visited[MAX]; 

void input(){
	cin >> n; 

	for(int i = 0; i < n + 2; i++){
		int x, y; 
		cin >> x >> y; 
		coord.push_back({x, y}); 
	}
}

int dist(pii p1, pii p2){
	int dx = abs(p1.first - p2.first); 
	int dy = abs(p1.second - p2.second); 
	return dx + dy; 
}

void dfs(int x){ 
	visited[x] = true; 

	for(int i = 0; i < graph[x].size(); i++){
		int y = graph[x][i]; 
		if(!visited[y]){ 
			dfs(y); 
		}
	}
}

void reset(){
	coord.clear(); 
	
	for(int i = 0; i < n + 2; i++){ 
		graph[i].clear(); 
	} 
	
	memset(visited, 0, sizeof(visited)); 
}

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

	int t; 
	cin >> t; 

	while(t--){
		input();

		for(int i = 0; i < n + 2; i++){ 
			for(int j = i + 1; j < n + 2; j++){ 
				// 거리가 1000이내인 지점들만 연결 
				if(dist(coord[i], coord[j]) <= 50 * 20){
					graph[i].push_back(j); 
					graph[j].push_back(i); 
				}
			}
		}

		dfs(0); 

		if(!visited[n + 1]) cout << "sad\n";
		else cout << "happy\n"; 

		reset();
	}
	
    return 0;
}