(C++) - 백준(BOJ) 9205번 : 맥주 마시면서 걸어가기 답

www.acmicpc.net/problem/9205

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

floyd warshell을 사용해 푸는 문제였습니다.

 

풀이방법 

 1. 모든 좌표 사이의 거리를 계산한 후 거리가 1000이하라면 1, 아니면 0으로 저장합니다.

 2. 모든 거리 정보들을 floyd warshell로 탐색합니다. i에서 k로 가는 경로 와 k에서 j로 가는 경로 모두 갈 수 있다면 i에서 j로도 갈 수 있으므로 정보를 갱신해줍니다. 즉, [i][j]를 1로 만들어 줍니다.

 3. 목적지까지 갈 수 있으면 happy 아니라면 sad를 출력합니다.

 

Code 

#include <iostream>
#include <cmath>
#include <vector>
#include <cstring>
using namespace std;

bool canGo(int distance){
    return distance <= 1000 ? true : false;
}

void storeDistances(int n, vector <pair<int,int>> &map, int checkPath[105][105]){
    for(int i = 0; i < n + 2; i++){
        for(int j = i + 1; j < n + 2; j++){
            int distance = abs(map[i].first - map[j].first) + abs(map[i].second - map[j].second);
            checkPath[j][i] = checkPath[i][j] = canGo(distance);
        }
    }
}

void floydWarshell(int n, int checkPath[105][105]){
    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(checkPath[i][k]&&checkPath[k][j]) checkPath[i][j] = 1;
}

int main(){
    int t,n;
    cin >> t;
    while(t--){
        cin >> n;

        vector <pair<int,int>> map(n+2,{0,0});
        int checkPath[105][105];
        memset(checkPath,0,sizeof(checkPath));

        for(int i = 0; i < n + 2; i++) cin >> map[i].first >> map[i].second;
        
        storeDistances(n, map, checkPath);
        floydWarshell(n, checkPath);

        if(checkPath[0][n+1]) cout << "happy\n";
        else cout << "sad\n";
    }
}