9205번

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

문제를 읽으면서 x,y 범위가 막 주어지고 어떤식으로 노드를 구성해야 할까 고민했다.

좌표별로 구하려고 하면 메모리가 넘칠 것 같아서 조금 더 생각해보니 , 간단한 플로이드 알고리즘 문제였다.

왜냐하면 편의점과 출발점 도착점을 모두 합쳐서 최대 노드가 102개 밖에 나오지 않기 때문이다.

우선 입력받은 n을 통해서 n+2 개의 노드를 만들고, x,y 값들을 입력받는다.

이때 n이 0 이면 출발점, n+1 일때는 마지막 페스티벌의 도착점.

그 다음 모든 노드들이 갈 수 있는지를 체크한다, 이 때 기준은 맥주 50잔 이기 때문에 거리가 1000 이하여야 한다.

이 값들을 플로이드 알고리즘을 사용하는 D배열에 저장한다.

플로이드 알고리즘을 구하고, 시작점0 에서 끝점 n+1 까지 도달가능한지 여부만 체크해주면 된다.

<정답 코드>

#include<iostream>
#include<vector>
using namespace std;
 
const int INF = 987654321;    
typedef struct
{
    int x;
    int y;
}pos;
int main()
{
    //freopen("input.txt", "r", stdin);
    int tc;
    cin >> tc;
    while (tc--)
    {
        int n;
        cin >> n;
        vector<pos> v(n + 2);
        vector<vector<int>> D(n + 2, vector<int>(n + 2,INF));
 
        for (int i = 0; i < n + 2; i++)
        {
            cin >> v[i].x >> v[i].y;
        }
 
        for (int i = 0; i < n + 2; i++)
        {
            for (int j = 0; j < n + 2; j++)
            {
                int dis = abs(v[i].x - v[j].x) + abs(v[i].y - v[j].y);
 
                if (dis <= 1000)
                {
                    D[i][j] = dis;
                }
            }
        }
 
        for (int k = 0; k < n + 2; k++)
        {
            for (int i = 0; i < n + 2; i++)
            {
                for (int j = 0; j < n + 2; j++)
                {
                    if (D[i][j] > D[i][k] + D[k][j])
                    {
                        D[i][j] = D[i][k] + D[k][j];
                    }
                }
            }
        }
 
        if (D[0][n + 1] != INF)
        {
            cout << "happy\n";
        }
        else
        {
            cout << "sad\n";
        }
 
    }
 
    return 0;
}