[ 백준 1277 ] 발전소 설치 (C++) - 그래프 이론, 구현

---

🔗 문제 링크

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

---

💡 문제 풀이 및 해석

1. 1과 N이 만나야 한다.
2. 두 발전소 사이의 거리(좌표상 거리)가 M미만이면, 두 발전소 사이에는 간선이 있다.
3. 이미 이어진 발전소는 길이가 0인 간선이 있다고 생각한다.
4. 이제 1에서 시작하는 평범한 bfs문제가 된다. (최적화를 하고 싶다면 다익스트라로 풀어야한다.) vector<vector<pair<int, double> > > edge(1001); // 발전소, 거리 이 부분을 내부를 vector<priority_queue<pair<double,int>>> edge(1001) // 거리, 발전소 이와같이 바꾸면 짧은 거리부터 찾아가면서 실제로 더 빠를 것 같다.

---

⭐️ 정답 코드 및 설명

#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#define INF 98754321

using namespace std;

int N, W;
double M;
vector<pair<int, int> > ps; // 발전소
vector<vector<pair<int, double> > > edge(1001); // 발전소, 거리
double visited[1001];

void make_edge(int x, int y, int num) {
    for (int i = 1; i <= ps.size(); i++) {
        int cx = ps[i - 1].first, cy = ps[i - 1].second;
        double dist = sqrt(pow(x - cx, 2) + pow(y - cy, 2));
        if (dist < M) {
            edge[num].push_back({i, dist});
            edge[i].push_back({num, dist});
        }
    }
}

void input() {
    cin >> N >> W >> M;

    for (int i = 1; i <= N; i++) {
        int x, y;
        cin >> x >> y;
        make_edge(x, y, i);
        ps.push_back({x, y});
    }

    for (int i = 0; i < W; i++) {
        int a, b;
        cin >> a >> b;
        edge[a].insert(edge[a].begin(), {b, 0.0});
        edge[b].insert(edge[b].begin(), {a, 0.0});
    }

    for (int i = 2; i <= N; i++) {
        visited[i] = INF;
    }
}

void sol() {
    queue<int> q;
    q.push(1);

    while (!q.empty()) {
        int cur = q.front();
        q.pop();

        for (int i = 0; i < edge[cur].size(); i++) {
            double dist = edge[cur][i].second;
            int next = edge[cur][i].first;

            if (visited[cur] + dist < visited[next]) {
                visited[next] = visited[cur] + dist;
                q.push(next);
            }
        }
    }
}

int main() {

    input();
    sol();
    cout << (int) (visited[N] * 1000);

    return 0;
}

---

🤔 문제 후기

못풀어서 문제를 구글링해보다가 참고 블로그에서 이미 이어진 간선의 길이를 0으로 둔다는 설명을 듣자마자 풀었다. 왜 이런 생각을 못했는지는 모르겠지만, 이 부분을 해결하기 위해서 누적거리랑 이전 발전소와의 거리 그리고 그 사이의 최솟값 등... 삽질을 4시간을 했다. 가끔은 간단하게 생각하면 쉽게 해결할 수 있는 문제들이 꽤 있다는 것을 다시 한번 깨달은 문제였다.