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

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

매우 간단한 BFS, DFS, 다익스트라, 플로이드-와샬 등으로 다양한 방법으로 풀 수 있다.

1. BFS나 DFS로 탐색할 경우 탐색이 끝난 후 visited[] 배열에 도착지가 true인가 false인가 확인하면 된다.

2. 다익스트라로 탐색할 경우 탐색이 끝난 후 도착지 정점의 dist가 INF인지 아닌지 확인하면 된다.

3. 플로이드-와샬로 탐색할 경우 탐색이 끝난 후 matrix[출발지][도착지]가 INF인지 아닌지 확인하면 된다.

기본적으로 1000m 이내에 있으면 간선으로 연결시켜주고 그 외의 경우에는 연결할 필요가 없다.

또한 간선에 대한 가중치도 필요가 없다. 왜냐하면 콜라를 리필하는데 대한 비용같은 것은 염두에 두지 않기 때문이다.

따라서 굳이 다익스트라나 플로이드-와샬로 풀빠에 그냥 BFS나 DFS로 완전탐색을 한다음 목적지 방문여부만

체크하는 것이 가장 쉽고 간단한 방법인것 같다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59

#include <iostream> #include <queue> #include <vector> #include <cmath> #define MAX 103 using namespace std; struct Vertex{ int x, y; vector<int> next; }; Vertex vertex[MAX]; bool visited[MAX]; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); int tc; cin >> tc; while(tc--){ int n; cin >> n; for(int i = 1; i <= n+2; i++){ vertex[i].next.clear(); visited[i] = false; } cin >> vertex[1].x >> vertex[1].y; for(int i = 3; i <= n+2; i++){ cin >> vertex[i].x >> vertex[i].y; } cin >> vertex[2].x >> vertex[2].y; for(int i = 1; i <= n+1; i++){ for(int j = i+1; j <= n+2; j++){ int dist = abs(vertex[i].x-vertex[j].x)+abs(vertex[i].y-vertex[j].y); if(dist <= 1000){ //possible vertex[i].next.push_back(j); vertex[j].next.push_back(i); } } } queue<int> q; q.push(1); visited[1] = true; while(!q.empty()){ int curIdx = q.front(); q.pop(); for(int nIdx : vertex[curIdx].next){ if(!visited[nIdx]){ visited[nIdx] = true; q.push(nIdx); } } } if(visited[2]) cout << "happy" << '\n'; else cout << "sad" << '\n'; } return 0; }