맥주 마시면서 걸어가기

• silver인데 많이 해매서 정답을 참고함
• 아직 그래프에 대한 문제의 이해가 부족하고 사용에 미숙함

코드

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
using namespace std; 
// 한 정점에서 다른 한 정점으로 갈 수 있는지 검사 --> (가중치가 다를 경우)다익스트라 / (가중치가 같으면)DFS
// DFS는 정점간 탐색비용이 1인 경우라고 보면 된다. 즉, 정점간 간선의 가중치가 다르면 다익스트라 써야함
// 벨만포드 --> 다익스트라보다 조금 느리지만 음수 간선에서 사용 가능
// 플로이드 워셜 --> 모든 정점끼리의 최단거리를 구하는 것
/* 정리 : 이 문제는 조건에 따라서 내가 각 정점끼리 갈수 있는지 여부를 graph에 저장할 수 있고
         해당 정보를 통해 이동할 수 있는지 검사 --> DFS */
int N;
vector<int> graph[103];
bool vis[103];
/* 일반적인 DFS --> 연결된 정점들을 표시할 수 있다 */
void DFS(int depth){
    vis[depth] = true;
    for(int i=0;i<graph[depth].size();i++)
    {
        int next = graph[depth][i];
        if(vis[next]) continue;
        DFS(next);
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int T;
    cin >> T;
    while(T--)
    {
        fill(vis, vis+103, false);
        for(int i=0;i<103;i++)
            graph[i].clear(); // vector를 비우는 명령어(공간도 없어짐)
        vector<pair<int,int>> tmp;
        cin >> N;
        for(int i=0;i<N+2;i++)
        {
            int y,x;
            cin >> y >> x;
            tmp.push_back({y,x});
        }
        for(int i=0;i<N+1;i++)
        {
            for(int j=i+1;j<N+2;j++)
            {
                if(abs(tmp[i].first-tmp[j].first)+abs(tmp[i].second-tmp[j].second) <= 50*20)
                {
                    graph[i].push_back(j);
                    graph[j].push_back(i); // 양방향 그래프
                }
            }
        }
        DFS(0);
        if(vis[N+1])
            cout << "happy"<<'\n';
        else
            cout << "sad" << '\n';
    }
    return 0;
}

• 핵심
  • 각 정점끼리 이동할 수 있는 조건은 맥주 20개로 즉, 1000미터 안에 있는 점이라는 것
  • 조건에 따라 연결된 간선을 양방향으로 넣어두고 출발지 ~ 도착지까지 연결되어 있는지 검사
• 깨달은 것
  • 다익스트라 / 벨만포드 / 플로이드 워셜 등이 어떨 때 쓰이는지 정리할 수 있었음
  • vector.clear()를 통해서 size를 0으로 만들 수 있음 --> push_back 가능
    (단, capacity는 그대로라서 메모리적으로 효율을 가질수는 없음, 사용에 이점만 가능)