[알고리즘][C++] 백준 9205 맥주 마시면서 걸어가기 문제 풀이

문제 출처 : www.acmicpc.net/problem/9205

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

---

문제 해석 : 맥주를 마시면서 걸어가면서 목적지 까지 도달할 수 있는지 결과를 출력하는 문제이다. 

 

문제 풀이 :  플루이드 워셜 알고리즘을 사용하면 풀이할 수 있다.

 

풀이 시간 (기록용) : 45분

 

---

풀이 코드

#include <vector>
#include <iostream>
#include <cstdlib>
#include <algorithm>

#define INF 987654321
using namespace std;

int main()
{
    int T;
    cin >> T;

    for (int test_case = 0; test_case < T; test_case++)
    {
        int N;
        cin >> N;

        vector<vector<int>> arr;
        int x = 0;
        int y = 0;

        for (int i = 0; i < N + 2; i++)
        {
            cin >> x >> y;
            vector<int> temp;
            temp.push_back(x);
            temp.push_back(y);
            arr.push_back(temp);
        }

        int possible[103][103];

        for (int i = 0; i < N + 2; i++)
        {
            for (int j = 0; j < N + 2; j++)
            {
                possible[i][j] = INF;
            }
        }

        for (int i = 0; i < N + 2; i++)
        {
            for (int j = 0; j < N + 2; j++)
            {
                if (i != j)
                {
                    int diff;
                    diff = abs(arr[i][0] - arr[j][0]) + abs(arr[i][1] - arr[j][1]);
                    if (diff <= 1000)
                    {
                        possible[i][j] = 1;
                    }
                }
            }
        }

        for (int k = 0; k < N + 2; k++)
        {
            for (int a = 0; a < N + 2; a++)
            {
                for (int b = 0; b < N + 2; b++)
                {
                    possible[a][b] = min(possible[a][b], possible[a][k] + possible[k][b]);
                }
            }
        }

        if (possible[0][N + 1] == INF)
        {
            cout << "sad" << endl;
        }
        else
        {
            cout << "happy" << endl;
        }
    }
    return 0;
}

---

author : donghak park
contact : donghark03@naver.com

## 문제의 저작권은 백준 알고리즘 사이트에 있습니다. 혹시 문제가 되는 부분이 있으면 연락 바랍니다.