BOJ 1753번 최단경로 문제

다익스트라로 풀 수 있는 문제다. 구현이 생각보다 잘 안돼서 다른 코드를 참조했다.

1753.cpp

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define MAXX 20001

int v, e, k;
int from, to, cost;
vector<pair<int, int>> graph[MAXX];

vector<int> dijkstra(int start, int vertex) {
    vector<int> distance(vertex, INF);  // start ~ 각 vertex 까지의 거리 저장, 초기값 INF
    distance[start] = 0;                // start ~ start = 0

    // 최소 힙 생성 pair<cost, vertex>
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, start});

    while (!pq.empty()) {
        int cost = pq.top().first;
        int currentVertex = pq.top().second;
        pq.pop();

        // 이미 더 작을 경우 넘어가자.
        if (distance[currentVertex] < cost) {
            continue;
        }

        int neighborNum = graph[currentVertex].size();
        for (int i = 0; i < neighborNum; i++) {
            int neighbor = graph[currentVertex][i].first;             // to
            int distanceToN = cost + graph[currentVertex][i].second;  // cost

            if (distance[neighbor] > distanceToN) {
                distance[neighbor] = distanceToN;
                pq.push({distanceToN, neighbor});
            }
        }
    }
    return distance;
}

int main() {
    cin >> v >> e >> k;
    for (int i = 0; i < e; i++) {
        cin >> from >> to >> cost;
        // from에서 to로 가는 cost를 저장한다.
        graph[from].push_back({to, cost});
    }
    // 0부터 시작해서 v에 1을 더해줘야 한다.
    vector<int> result = dijkstra(k, v + 1);
    for (int i = 1; i < v + 1; i++) {
        if (result[i] == INF) {
            cout << "INF" << '\n';
        } else {
            cout << result[i] << '\n';
        }
    }
}
저작자표시

'알고리즘 & SQL > 백준(BOJ)' 카테고리의 다른 글

백준 1547번 : 공 C++  (0) 2018.12.01
백준 1197번 : 최소 스패닝 트리 C++  (0) 2018.11.28
백준 1922번 : 네트워크 연결 C++  (0) 2018.11.28
백준 16398번 : 행성 연결 C++  (0) 2018.11.28
백준 1916번 : 최소비용 구하기 C++  (0) 2018.11.28

BOJ 1922번 네트워크 연결 문제

MST로 풀면 된다.

1922.cpp

#include <bits/stdc++.h>
using namespace std;
#define MAXX 1001
typedef long long ll;
struct Edge {
    int v1;
    int v2;
    int c;
    bool operator<(Edge &e) {
        return c < e.c;
    }
};

int n, m;
int parent[MAXX];
int setSize[MAXX];
vector<Edge> ev;

void init();                // parent, setSize 배열 초기화
int find_(int n);           // 부모를 찾는 함수
void union_(int a, int b);  // 집합을 합치는 함수

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int v1, v2, c;
        cin >> v1 >> v2 >> c;
        ev.push_back({v1, v2, c});
    }
    sort(ev.begin(), ev.end());
    init();
    ll result = 0;
    for (int i = 0; i < m; i++) {
        // 같은 집합이 아니면
        if (find_(ev[i].v1) != find_(ev[i].v2)) {
            union_(ev[i].v1, ev[i].v2);
            result += ev[i].c;
        }
    }
    cout << result;
}

void init() {
    for (int i = 0; i < n; i++) {
        parent[i] = i;
        setSize[i] = 0;
    }
}

int find_(int n) {
    if (n == parent[n]) {
        return n;
    }
    return parent[n] = find_(parent[n]);
}

void union_(int a, int b) {
    a = find_(a);
    b = find_(b);
    if (a != b) {
        // 크기가 작은 쪽이 큰 쪽으로 합치게끔 구현한다.
        if (setSize[a] < setSize[b]) {
            swap(a, b);
        }
        parent[b] = a;
        setSize[a] += setSize[b];
        setSize[b] = 0;
    }
}
저작자표시

'알고리즘 & SQL > 백준(BOJ)' 카테고리의 다른 글

백준 1197번 : 최소 스패닝 트리 C++  (0) 2018.11.28
백준 1753번 : 최단경로 C++  (0) 2018.11.28
백준 16398번 : 행성 연결 C++  (0) 2018.11.28
백준 1916번 : 최소비용 구하기 C++  (0) 2018.11.28
백준 16499번 : 동일한 단어 그룹화하기 C++  (0) 2018.11.27

BOJ 16398번 행성 연결 문제

2018 홍익대학교 E번 문제였다. MST로 어렵지 않게 풀 수 있다.

16398.cpp

#include <bits/stdc++.h>
using namespace std;
#define MAXX 1001
typedef long long ll;
struct Edge {
    int v1;
    int v2;
    int c;
    bool operator<(Edge &e) {
        return c < e.c;
    }
};

int n;
int parent[MAXX];
int setSize[MAXX];
vector<Edge> ev;

void init();                // parent, setSize 배열 초기화
int find_(int n);           // 부모를 찾는 함수
void union_(int a, int b);  // 집합을 합치는 함수

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int cost;
            cin >> cost;
            if (i < j) {
                ev.push_back({i, j, cost});
            }
        }
    }
    sort(ev.begin(), ev.end());
    init();
    ll result = 0;
    for (int i = 0; i < ev.size(); i++) {
        // 같은 집합이 아니면
        if (find_(ev[i].v1) != find_(ev[i].v2)) {
            union_(ev[i].v1, ev[i].v2);
            result += ev[i].c;
        }
    }
    cout << result;
}

void init() {
    for (int i = 0; i < n; i++) {
        parent[i] = i;
        setSize[i] = 0;
    }
}

int find_(int n) {
    if (n == parent[n]) {
        return n;
    }
    return parent[n] = find_(parent[n]);
}

void union_(int a, int b) {
    a = find_(a);
    b = find_(b);
    if (a != b) {
        // 크기가 작은 쪽이 큰 쪽으로 합치게끔 구현한다.
        if (setSize[a] < setSize[b]) {
            swap(a, b);
        }
        parent[b] = a;
        setSize[a] += setSize[b];
        setSize[b] = 0;
    }
}
저작자표시

'알고리즘 & SQL > 백준(BOJ)' 카테고리의 다른 글

백준 1753번 : 최단경로 C++  (0) 2018.11.28
백준 1922번 : 네트워크 연결 C++  (0) 2018.11.28
백준 1916번 : 최소비용 구하기 C++  (0) 2018.11.28
백준 16499번 : 동일한 단어 그룹화하기 C++  (0) 2018.11.27
백준 6996번 : 에너그램 C++  (0) 2018.11.26

BOJ 1916번 최소비용 구하기 문제

다익스트라 알고리즘으로 풀면 된다. 전에 풀었던 코드를 가져와서 수정했다.

1916.cpp

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define MAXX 20001

int n, m;
int from, to, cost;
vector<pair<int, int>> graph[MAXX];

vector<int> dijkstra(int start, int vertex) {
    vector<int> distance(vertex, INF);  // start ~ 각 vertex 까지의 거리 저장, 초기값 INF
    distance[start] = 0;                // start ~ start = 0

    // 최소 힙 생성 pair<cost, vertex>
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, start});

    while (!pq.empty()) {
        int cost = pq.top().first;
        int currentVertex = pq.top().second;
        pq.pop();

        // 이미 더 작을 경우 넘어가자.
        if (distance[currentVertex] < cost) {
            continue;
        }

        int neighborNum = graph[currentVertex].size();
        for (int i = 0; i < neighborNum; i++) {
            int neighbor = graph[currentVertex][i].first;             // to
            int distanceToN = cost + graph[currentVertex][i].second;  // cost

            if (distance[neighbor] > distanceToN) {
                distance[neighbor] = distanceToN;
                pq.push({distanceToN, neighbor});
            }
        }
    }
    return distance;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> from >> to >> cost;
        // from에서 to로 가는 cost를 저장한다.
        graph[from].push_back({to, cost});
    }
    // 0부터 시작해서 v에 1을 더해줘야 한다.
    int start, end;
    cin >> start >> end;
    vector<int> result = dijkstra(start, n+1);
    cout << result[end];
}
저작자표시

'알고리즘 & SQL > 백준(BOJ)' 카테고리의 다른 글

백준 1922번 : 네트워크 연결 C++  (0) 2018.11.28
백준 16398번 : 행성 연결 C++  (0) 2018.11.28
백준 16499번 : 동일한 단어 그룹화하기 C++  (0) 2018.11.27
백준 6996번 : 에너그램 C++  (0) 2018.11.26
백준 6359번 : 만취한 상범 C++  (0) 2018.11.26

BOJ 16499번 동일한 단어 그룹화하기 문제

어떻게 해야 이 문제를 쉽게 풀 수 있을까 생각했는데, 결론은 문자열을 정렬한 후 map에 저장하고 map의 size를 출력하는게 제일 쉬운거 같다.

16499.cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    map<string, int> word;
    while (n--) {
        string s;
        cin >> s;
        sort(begin(s), end(s));
        word[s] = 1;
    }
    cout << word.size();
}
저작자표시

'알고리즘 & SQL > 백준(BOJ)' 카테고리의 다른 글

백준 16398번 : 행성 연결 C++  (0) 2018.11.28
백준 1916번 : 최소비용 구하기 C++  (0) 2018.11.28
백준 6996번 : 에너그램 C++  (0) 2018.11.26
백준 6359번 : 만취한 상범 C++  (0) 2018.11.26
백준 5597번 : 과제 안 내신 분..? C++  (0) 2018.11.26

+ Recent posts

티스토리툴바