9205_맥주마시면서 걸어가기

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

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

 

접근

 

- 10000(50*20) 미터 이내에 있는 거리는 도달 할 수 있다

- 출발점으로 부터 각각의 좌표 정보를 확인하는 과정 중에

    - 행복 거리(10000) 이내로 갈 수 있다면 양방향 간선에 추가한다

- 최종적으로 페스티벌에 도착할 수 있는지 확인 한다

 

- sudo code

 

for(int i = 0 ; i < n+2 ; i++){

    for(int j = i+1; j < n+2; j++){

        만약 지점 i 와 지점 j 사이의 거리가 행복 거리라면

        양방향 노드로 추가

 

    }

 }

 

 dfs(int node){

    visit[node] = true

    for(int i = 0 ; i < adj[node].size() ; i++){

        if(!visit[i])}

            dfs(i);

        }

    }

 }

 

#include <iostream>
#include <vector>
#include <cstring>
#define MAX 102
#define SAFE 50 * 20

using namespace std;
struct pos {int y, x;};
vector<vector<int>> adj;
bool visited[MAX];

void dfs(int node){
    visited[node] = true;
    for(int i = 0 ; i < adj[node].size() ; i++){
        int there = adj[node][i];
        if(!visited[there]){
            dfs(there);
        }
    }
}

int main(int argc, const char * argv[]) {
    int t, n;
    scanf("%d", &t);
    for(int i = 0 ; i < t ; i++){
        scanf("%d", &n);
        vector<pos> points = vector<pos>(n+2);
        for(int j = 0 ; j < n+2 ; j++){
            scanf("%d %d", &points[j].y, &points[j].x);
        }
        adj = vector<vector<int>>(n+2);
        for(int a = 0 ; a < n+2; a++){
            for(int b = a+1; b < n+2; b++){
                int dist = abs(points[a].y - points[b].y) + abs(points[a].x - points[b].x);
                if(dist <= SAFE){
                    adj[a].push_back(b);
                    adj[b].push_back(a);
                }
            }
        }
        
        memset(visited, false, sizeof(visited));
        dfs(0);
        if(visited[n+1]){
            printf("happy\n");
        }else{
            printf("sad\n");
        }
        
        
    }
    return 0;
}