백준 9205 맥주 마시면서 걸어가기 - c++ 플로이드 와샬 풀이

문제 링크

www.acmicpc.net/problem/9205

풀이 아이디어

dfs bfs 말고 플로이드 와샬로 풀었다.

x,y좌표를 한꺼번에 담아야 하므로 pair<int,int> 꼴의 배열을 준비했다.

코드를 편하게 짜기 위해 갈수 있냐없냐를 bool 함수로 준비했고,

편의점 n개, 시작점 끝점 1개씩을 저장할 수 있는 d 이차원 배열 역시 준비했다.

 

적당히 큰 값으로 d 배열을 초기화 한 후,

한 포인트에서 다른 포인트로 갈 수 있으면 그 값을 1로 바꾸었다.

그리고 플로이드 와샬을 통해 경로를 최적화 한 후,

d[0][n+1] 값을 비교해 (출발-끝 거리) 결과를 뽑아내면 된다.

코드

#include <bits/stdc++.h>
using namespace std;

pair<int,int> point[102];
int t,n;
int d[102][102];

bool isavailable(int sidx,int eidx){
    if(abs(point[sidx].first-point[eidx].first) + abs(point[sidx].second - point[eidx].second)<=1000)
        return true;
    else return false;
}

int main(void){
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=0; i<n+2; i++){
            cin>>point[i].first>>point[i].second;
        }

        for(int i=0; i<n+2; i++){
            for(int j=0; j<n+2; j++){
                if(i!=j) d[i][j]=102;
            }
        }

        for(int i=0; i<n+2; i++){
            for(int j=0; j<n+2; j++){
                if(i==j) continue;
                if(isavailable(i,j)) d[i][j]=1;
            }
        }

        //플로이드와샬이 지금 들어감.
        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(0<d[0][n+1] && d[0][n+1]<102)
            cout<<"happy\n";
        else cout<<"sad\n";


    }
}