[BOJ] 9205 - 맥주 마시면서 걸어가기

Sierra·2022년 2월 2일
0

[BOJ] GraphTheory

목록 보기
11/30
post-thumbnail

https://www.acmicpc.net/problem/9205

문제

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

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

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

입력

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

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

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

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

출력

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

예제 입출력

  • 예제 입력 1
2
2
0 0
1000 0
1000 1000
2000 1000
2
0 0
1000 0
2000 1000
2000 2000
  • 예제 출력 1
happy
sad

Solution

#include <iostream>
#include <vector>
#include <cstring>
#define MAX 103

using namespace std;

bool visit[MAX];
vector<int> adj[MAX];

void init(){
    memset(visit, false, sizeof(visit));
    for(int i = 0; i < MAX; i++) adj[i].clear();
}

void DFS(int X){
    visit[X] = true;
    for(auto i : adj[X]){
        if(!visit[i]) DFS(i);
    }
}

int getDist(pair<int, int> a, pair<int, int> b){
    return abs(a.first - b.first) + abs(a.second - b.second);
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int TestCase;
    cin >> TestCase;
    for(int tc = 0; tc < TestCase; tc++){
        init();
        int N;
        cin >> N;
        vector<pair<int, int>> vec(N+2);
        for(auto & i : vec) cin >> i.first >> i.second;
        for(int i = 0; i < N+2; i++){
            for(int j = i + 1; j < N+2; j++){
                int dist = getDist(vec[i], vec[j]);
                if(dist <= 1000){
                    adj[i].push_back(j);
                    adj[j].push_back(i);
                }
            }
        }
        DFS(0);
        if(visit[N+1]) cout << "happy\n";
        else cout << "sad\n";
    }
}

뻘짓하다가 실컷 틀려먹은 문제.
memset 에 인수 잘못 넣어서 프로그램이 이상하게 동작해서 한동안 고생했다.

플로이드 와샬을 쓰라고는 하지만 솔직히 말해서 그렇게까지 해야하나 싶기도 하다. 사실 문제 자체가 까다로운게, 인접행렬을 만드는데 상당히 노가다가 필요하다.

우선 우리에겐 한 가지 조건이 있다. 맥주가 다 떨어질 정도로 먼 거리까진 움직이지 않는다는 것.
즉 맨헤튼 거리가 1000 보다 큰 위치까진 어차피 움직이지 않는다.

int N;
cin >> N;
vector<pair<int, int>> vec(N+2);
for(auto & i : vec) cin >> i.first >> i.second;
for(int i = 0; i < N+2; i++){
	for(int j = i + 1; j < N+2; j++){
		int dist = getDist(vec[i], vec[j]);
		if(dist <= 1000){
			adj[i].push_back(j);
			adj[j].push_back(i);
        }
    }
}

입력 받은 데이터를 vector에 저장해둔 후 이중for문을 돌려서 각자 위치에 대한 가중치를 계산한다. 비효율적이다 싶겠다만 어차피 N이 많아봐야 100이다. 써도 될 땐 확실히 써 주자.

그 후 각 노드간에 맨헤튼 거리가 1000 보다 작거나 같다면 인접행렬에 각 좌표를 저장해준다. 입력받은 순서대로 0부터 N+1까지의 좌표들에 대해 해당 작업을 해준다.

void DFS(int X){
    visit[X] = true;
    for(auto i : adj[X]){
        if(!visit[i]) DFS(i);
    }
}

그 후는 간단한 DFS를 한다.

if(visit[N+1]) cout << "happy\n";
else cout << "sad\n";

마지막 좌표는 페스티벌 장이므로 여기 방문한게 아니라면 도착하지 못했다는 의미다.
맥주를 좀 넉넉히 가져갔다면 모르겠으나 무겁게 그런 짓을 하고싶진 않겠지.

이 문제를 한동안 어떻게 플로이드 와샬로 풀어야하나 고민했었는데 그냥 대충 풀었다. 그렇게 안 해도 되는 문제였다.

막상 문제를 풀고나니 허무했던 문제. 페스티벌 보러 가고싶다. 망할 코로나가 빨리 정리되어서 2022년에는 페스티벌을 즐길 수 있기를 바래보자.

profile
블로그 이전합니다 : https://swj-techblog.vercel.app/

0개의 댓글