백준) 9205 맥주 마시면서 걸어가기

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

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

문제

송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 록 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. 맥주 한 박스에는 맥주가 20개 들어있다. 목이 마르면 안 되기 때문에 50미터에 한 병씩 마시려고 한다.

상근이의 집에서 페스티벌이 열리는 곳은 매우 먼 거리이다. 따라서, 맥주를 더 구매해야 할 수도 있다. 미리 인터넷으로 조사를 해보니 다행히도 맥주를 파는 편의점이 있다. 편의점에 들렸을 때, 빈 병은 버리고 새 맥주 병을 살 수 있다. 하지만, 박스에 들어있는 맥주는 20병을 넘을 수 없다.

편의점, 상근이네 집, 펜타포트 락 페스티벌의 좌표가 주어진다. 상근이와 친구들이 행복하게 페스티벌에 도착할 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 t가 주어진다. (t ≤ 50)

각 테스트 케이스의 첫째 줄에는 맥주를 파는 편의점의 개수 n이 주어진다. (0 ≤ n ≤ 100).

다음 n+2개 줄에는 상근이네 집, 편의점, 펜타포트 록 페스티벌 좌표가 주어진다. 각 좌표는 두 정수 x와 y로 이루어져 있다. (두 값 모두 미터, -32768 ≤ x, y ≤ 32767)

송도는 직사각형 모양으로 생긴 도시이다. 두 좌표 사이의 거리는 x 좌표의 차이 + y 좌표의 차이이다. (맨해튼 거리)

출력

각 테스트 케이스에 대해서 상근이와 친구들이 행복하게 페스티벌에 갈 수 있으면 "happy", 중간에 맥주가 바닥나면 "sad"를 출력한다. 

 

풀이>>

DFS 로 구현 해주 었다. 모든 정점을 vector로 pair로 묶어 x 좌표 y좌표를 각각 넣어 주었다. vector에 모든 정점을 넣어 주었다면 문제 조건 50m마다 맥주 1병 씩을 먹는 우리 주인공을 위해 최대 맥준 20병 가지고 1000m까지 밖에 움직일 수 없다는 조건을 구할 수 있다. 해당 정점에서 다음 정점까지  1000m 이하이면 이 정점은 사용할 수 있는 정점 이 된다.

양방향으로 벡터를 넣어준다. 이후에 DFS로 방문을 해주며 해당 케이스 목표 지점인 N+1로 갈 수 있는 봐주어야 한다.

출발지 0

편의점 N

목적지 N+1  

 

이므로  목적지 가 1이면 happy이고 그렇지 못하다면 sad를 출력해주어야 한다.  배열 크기를 103의 의미는 편의점 + 2이다.

 

#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
using namespace std;
 
vector<int> s[103];
int visited[103];
 
int abs(int n)
{
    if(n<0)
    return -n;
 
    return n;
}
 
void dfs(int x)
{
 
    visited[x] =1;
 
    int i;
 
    for(i = 0 ; i < s[x].size() ;i++)
    {
                int y = s[x][i]; 
        
            if(visited[y]) continue;
 
            dfs(y);
 
    }
 
}
 
 
 
 
int main()
{
    int i,j;
    int kase;
    scanf("%d" ,&kase);
 
 
        while(kase--)
        {
            vector<pair<int ,int> > a;
 
            int N;
            scanf("%d" ,&N); //편의점 개수
 
            int homex,homey;
            scanf("%d%d" ,&homex, &homey);
 
            a.push_back( make_pair(homex , homey) );
 
 
                    int x, y;
                for( i = 1; i<= N; i++)
                {
                    scanf("%d%d" ,&x,&y);
                        a.push_back(make_pair(x,y));
                }
 
 
                int desx , desy;
                scanf("%d%d",&desx ,&desy);
                a.push_back(make_pair(desx , desy));
 
                int len = N+2;
 
                for( i = 0 ; i < len-1 ;i++ )
                for( j = i+1 ; j < len ;j++ )
                if(  abs(a[i].first - a[j].first )  + abs(a[i].second - a[j].second)  <= 1000  )
                {
                        s[i].push_back(j);      s[j].push_back(i);
 
                }
 
                dfs(0);
 
        if(visited[len-1])
            printf("happy\n");
        else printf("sad\n");
        
 
 
 
            for(i=0 ;i< 103; i++)
                s[i].clear();
 
            a.clear();
            memset(visited , 0 ,sizeof(visited));
        }
 
 
    return 0 ;
}