[백준] 14466 소가 길을 건너간 이유 6

 

옛날에 이상하게 풀고 틀렸던 문제다

 

오늘 다시보니 다익스트라가 먼저 떠올라서 풀었다

 

N의 크기가 작아서 덕분에 풀었다

 

다익스트라를 모든 소에서 돌리면서 다리가 있다면 비용을 1 없다면 0으로 탐색하면된다

그리고 소의 위치를 돌며 가는데 비용이 든다면 set에 저장해주자

 

그럼 set의 사이즈가 정답이 된다!

 

풀고나서 사람들을보니 다들 시간도 메모리도 적게쓰고 bfs 혹은 유니온파인드로 풀었다

 

유니온파인드 공부 부수러가야겠다

 

소스코드

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <set>
using namespace std;
int n, k, r;
int map[111][111];
int d[111][111];
bool c[111][111][111][111];
int dx[4] = { 0,0,-1,1 };
int dy[4] = { 1,-1,0,0 };
pair<int, int> cow[111];
set<pair<int, int>> s;
bool inner(int x, int y) {
    return (1 <= x && x <= n && 1 <= y && y <= n);
}
void solve(int _x, int _y,int now) {
    memset(d, -1, sizeof(d));
    priority_queue<pair<int, pair<int, int>>> pq;
    pq.push({ 0,{_x,_y} });
    while (!pq.empty()) {
        int cost = -pq.top().first;
        int x = pq.top().second.first;
        int y = pq.top().second.second;
        pq.pop();
 
        if (d[x][y] != -1) continue;
        d[x][y] = cost;
 
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            int ncost = -cost;
            if (inner(nx, ny) && d[nx][ny] == -1) {
                if (c[x][y][nx][ny] || c[nx][ny][x][y]) ncost -= 1;
                pq.push({ ncost,{nx,ny} });
            }
        }
    }
    for (int i = 0; i < k; i++) {
        if (i == now) continue;
        int x = cow[i].first;
        int y = cow[i].second;
        if (d[x][y] > 0) s.insert({ min(i,now),max(i,now) });
    }
}
int main() {
    //freopen("input.txt", "r", stdin);
    scanf(" %d %d %d", &n, &k, &r);
    for (int i = 0; i < r; i++) {
        int u, v, x, y; scanf(" %d %d %d %d", &u, &v, &x, &y);
        c[u][v][x][y] = c[x][y][u][v] = 1;
    }
    for (int i = 0; i < k; i++) scanf(" %d %d", &cow[i].first, &cow[i].second);
    for (int i = 0; i < k; i++) solve(cow[i].first, cow[i].second,i);
    printf("%d\n", s.size());
}

 

+++

유니온파인드를 이용해 풀어봤는데 진짜 빠르다!

 

먼저 모든 땅에서 다리설치를 확인한다

배열을 [101][101][4]로 잡아서 내가 있는 곳에서 4방향으로 다리가 있다면 true로 바꿔준다

 

그리고 n^2으로 보며 만약 다리가 없다면 merge를 통해 하나의 땅으로 합쳐준다

 

마지막으로 소들이 있는 자리에서 부모를 확인하면 된다!

 

소스코드

#include <iostream>
#include <algorithm>
using namespace std;
int n, k, r,ans;
int map[111][111][4];
pair<int, int> cow[111];
int p[10010];
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
 
bool inner(int x, int y) {
    return (0 <= x && x < n && 0 <= y && y < n);
}
 
int find(int x) {
    if (p[x] == x) return x;
    return p[x] = find(p[x]);
}
 
void merge(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return;
    p[x] = y;
}
 
int main() {
    scanf(" %d %d %d", &n, &k, &r);
    for (int i = 0; i <=10000; i++) p[i] = i;
    for (int i = 0; i < r; i++) {
        int u, v, x, y; scanf(" %d %d %d %d", &u, &v, &x, &y);
        u--; v--; x--; y--;
        if (u == x) {
            if (v > y) swap(v, y);
            map[u][v][2] = map[x][y][3] = 1;
        }
        if (v == y) {
            if (u > x) swap(u, x);
            map[u][v][0] = map[x][y][1] = 1;
        }
    }
    for (int i = 0; i < k; i++) {
        int x, y; scanf(" %d %d", &x, &y); x--; y--;
        cow[i] = { x,y };
    }
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < 4; k++) {
                int nx = i + dx[k];
                int ny = j + dy[k];
                if (inner(nx, ny) && !map[i][j][k]) merge(find(i*n + j), find(nx*n + ny));
            }
        }
    }
    for (int i = 0; i < k - 1; i++) {
        for (int j = i + 1; j < k; j++) {
            if (find(cow[i].first*n + cow[i].second) != find(cow[j].first*n + cow[j].second)) ans += 1;
        }
    }
    printf("%d\n", ans);
}