[백준 9205 C++][S1] 맥주 마시면서 걸어가기

⭐️ 난이도

Silver 1

 

---

⭐️ 문제

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

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

 

---

⭐️ Idea flow

 

이 문제에서는 간선이 주어지지 않았다. 직접 계산해서 추가를 해야 한다.

집, 편의점, 페스티벌의 위치가 주어지기 때문에, 각 지점에서 다른 지점까지의 거리가 맥주 20병으로 갈 수 있는 거리인지 확인한다.

만일 맥주 20병으로 갈 수 있는 거리라면(50m * 20병 = 1000m) 간선 정보에 추가해준다.

 

간선을 추가했다면 그 다음부터는 간단하다.

집에서부터 BFS/DFS를 실행해서 페스티벌에 도달할 수 있는지 확인하면 된다.

만일 도달한다면 happy를, 도달하지 못한다면 sad를 출력한다.

 

[전체적인 알고리즘]

1) 집, 편의점, 페스티벌의 좌표를 모두 받아서 vector<vector<pair<int, int>> pos에 저장

2) 이중 for문을 통해서 모든 경우의 수를 조사하여 거리가 1000m 이하인지 조사

   만일 조건에 부합한다면 간선 추가

3) 이후 BFS/DFS를 통해 집에서 페스티벌에 도달이 가능한지 확인

   if 도달: happy 출력, if 도달X: sad 출력

 

---

⭐️ Code

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <unordered_set>
#include <unordered_map>

#define INF 987654321
#define MAX 1000000 + 1
using namespace std;

// 9205 - 맥주 마시면서 걸어가기
int n = 0, result = 0;
vector<pair<int, int>> pos; // idx 0:home, idx n+1:festival
vector<vector<int>> graph;
vector<bool> isVisited;

void input(){
    cin >> n;
    pos.assign(n + 2, {0,0});
    graph.assign(n + 2, vector<int>(0, 0));
    isVisited.assign(n + 2, false);

    for(int i = 0; i < n + 2; i++){
        int y, x;
        cin >> y >> x;
        pos[i] = {y, x};
    }
}

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

void setEdge(){
    for(int i = 0; i < n + 2; i++){
        for(int k = i + 1; k < n + 2; k++){
            // 맥주 20병 * 50m
            if(getDistance(pos[i], pos[k]) <= 1000){
                graph[i].emplace_back(k);
                graph[k].emplace_back(i);
            }
        }
    }
}

void DFS(int idx){
    isVisited[idx] = true;

    for(int i = 0; i < graph[idx].size(); i++){
        int next = graph[idx][i];
        if(!isVisited[next]){
            DFS(next);
        }
    }
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int testcase = 0;
    cin >> testcase;

    while(testcase--){
        input();
        setEdge();
        DFS(0);

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

    return 0;
}

 

---

⭐️ Feedback

 

문제를 읽었을 때에는 간단한 그래프 문제라고 생각을 했지만, 막상 문제를 풀려고 하니 간선이 없는 그래프였다!

하지만 문제에서 간선을 만들 수 있는 충분한 힌트도 주었으니, 간선이 없다면 간선을 만들면 된다.

 

앞으로도 다른 문제를 만났을 때, 너무 당황하지말고 힌트가 충분히 주어졌을테니, 힌트를 찾아보자.