지형 이동

https://programmers.co.kr/learn/courses/30/lessons/62050

programmers 프로그래머스 최소신장트리 mst sw역량테스트 코딩 코테 복습 구현 생각 필수

java 자바 collections Collections 컬렉션 java vector sort 자바 프로그래머스 유니온 파인드

처음에 bfs로 접근하려다가, 순간 최소신장트리(mst) 문제임을 알았다.(아래의 문제를 풀었기 때문)

비슷한 문제 : https://hsdevelopment.tistory.com/416

나는 사이클 여부를 union-find를 활용하였다.

연결된 다리의 개수는 전체 정점의 개수 - 1 이어야만 한다.

참고로 Java에서 몇 개 틀렸었는데, p 배열을 초기화 할 때, 연결요소의 개수가 N+1개 이상일 수도 있다.

그래서 넉넉하게 N * N + N으로 초기화했다.

또한, 정렬할 때 C++에서는 단순 거리(first)로만 정렬했는데도 정답이었으나

Java에서는 틀리게 나왔었다. 그래서 Java에서는 second, third 모두 오름차순 정렬해줬다. 

#include <bits/stdc++.h>
 
using namespace std;
 
#define Max 303
 
typedef struct info
{
    int from, to, distance;
}info;
 
int dy[4] = { 0, 1, 0, -1 };
int dx[4] = { 1, 0, -1, 0 };
int p[Max * Max], m[Max][Max], R, C;
vector<vector<int> > v;
vector<info> d;
bool visit[Max][Max];
 
bool cmp(const info & a, const info & b)
{
    return a.distance < b.distance;
}
 
int Find(int x)
{
    if (x == p[x]) {
        return x;
    }
    return p[x] = Find(p[x]);
}
 
void Union(int a, int b)
{
    a = Find(a);
    b = Find(b);
 
    if (a < b) {
        p[b] = a;
    }
    else {
        p[a] = b;
    }
}
 
void dfs(int r, int c, int group, int h)
{
    visit[r][c] = true;
    m[r][c] = group;
 
    for (int i = 0; i < 4; i++) {
        int y = r + dy[i];
        int x = c + dx[i];
 
        if (y < 0 || y >= R || x < 0 || x >= C || visit[y][x] || abs(v[r][c] - v[y][x]) > h) {
            continue;
        }
 
        dfs(y, x, group, h);
    }
}
 
int solution(vector<vector<int> > land, int height) {
    int answer = 0;
    R = land.size();
    C = R;
 
    v = land;
 
    int idx = 1;
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            p[i*C + j + 1] = i*C + j + 1; // Union-Find
            if (!visit[i][j]) {
                // 그룹화
                dfs(i, j, idx, height);
                ++idx;
            }
        }
    }
 
    // 정점에서 다른 정점으로 사다리 타는 최소 비용 후보들을 d vector에 push_back
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            for (int k = 0; k < 4; k++) {
                int y = i + dy[k];
                int x = j + dx[k];
 
                if (y < 0 || y >= R || x < 0 || x >= C || m[i][j] == m[y][x]) {
                    continue;
                }
 
                int f = m[i][j], t = m[y][x];
 
                // 따로 최솟값을 구하는 과정을 안 거쳐도 그냥 d vector에 push_back -> 그 후 정렬
                d.push_back({ f, t, abs(land[i][j] - land[y][x]) });
            }
        }
    }
 
    sort(d.begin(), d.end(), cmp); // 정렬
 
    int con = 0;
    for (auto i : d)
    {
        if (Find(i.from) != Find(i.to)) {
            Union(i.from, i.to);
            answer += i.distance;
            if (++con == idx - 2) {
                break;
            }
        }
    }
 
    return answer;
}
 
int main()
{
    cin.tie(0);
 
    vector<vector<int> > v = {
        { 1, 4, 8, 10 },
        { 5, 5, 5, 5 },
        { 10, 10, 10, 10 },
        { 10, 10, 10, 20 }
    };
 
    //vector<vector<int> > v = {
    //    { 10, 11, 10, 11 },
    //    { 2, 21, 20, 10 },
    //    { 1, 20, 21, 11 },
    //    { 2, 1, 2, 1 }
    //    // 답 2
    //};
 
    printf("%d\n", solution(v, 3));
 
    return 0;
}

import java.io.*;
import java.util.*;
 
public class Solution {
    
    static boolean[][] visit;
    static int[][] group, Land;
    static int N;
    static int[] dy = {0, 1, 0, -1}, dx = {1, 0, -1, 0}, p;
    static Vector<info> v;
    
    static BufferedReader br;
    static BufferedWriter bw;
    
    static int Find(int x)
    {
        if(x==p[x]) return x;
        return p[x] = Find(p[x]);
    }
    
    static void Union(int a, int b)
    {
        a = Find(a);
        b = Find(b);
        
        if(a < b) {
            p[b] = a;
        }
        else {
            p[a] = b;
        }
    }
    
    static void dfs(int r, int c, int height, int gn)
    {
        group[r][c] = gn;
        visit[r][c] = true;
        
        for(int i=0; i<4; i++) {
            int y = r + dy[i];
            int x = c + dx[i];
            
            if(y < 0 || y >= N || x < 0 || x >= N || visit[y][x] || Math.abs(Land[r][c] - Land[y][x]) > height) {
                continue;
            }
            
            dfs(y, x, height, gn);
        }    
    }
    
    public static int solution(int[][] land, int height) {
        int answer = 0;
        N = land.length;
        
        Land = land;
        group = new int[N+3][N+3];
        visit = new boolean[N+3][N+3];
        p = new int[N*N + N];
        v = new Vector<info>();
        
        for(int i=0; i<=N; i++) {
            Arrays.fill(group[i], 0);
            Arrays.fill(visit[i], false);
        }
        
        int gn = 1;
        
        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                p[i*N + j + 1] = i*N + j + 1;
                
                if(!visit[i][j]) {
                    dfs(i, j, height, gn);
                    ++gn;
                }
            }
        }
        
        --gn;
        
        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                for(int k=0; k<4; k++) {
                    int y = i + dy[k];
                    int x = j + dx[k];
                    
                    if(y < 0 || y >= N || x < 0 || x >= N || group[i][j] == group[y][x]) {
                        continue;
                    }
                    
                    v.add(new info(Math.abs(land[i][j] - land[y][x]), group[i][j], group[y][x]));
                }
            }
        }
 
        Collections.sort(v, new Comparator<info>() {
            public int compare(info p1, info p2) {
                 if(p1.first < p2.first) {
                     return -1; // 오름차순
                 }
                 else if(p1.first == p2.first) {
                     if(p1.second < p2.second) {
                         return -1;
                     }
                     else if(p1.second == p2.second) {
                         if(p1.third < p2.third) {
                             return -1;
                         }
                     }
                 }
                 return 1;
            }
        });
        
        int cnt = 0;
        for(info i : v) {
            if(Find(i.second) != Find(i.third)) {
                Union(i.second, i.third);
                answer += i.first;
                if(++cnt == gn - 1) {
                    break;
                }
            }
        }
        
        return answer;
    }
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        
        int[][] land = {
                { 10, 11, 10, 11 },
                { 2, 21, 20, 10 },
                { 1, 20, 21, 11 },
                { 2, 1, 2, 1 }
        };
        
        System.out.println(solution(land, 1));
    
//        bw.write(String.valueOf(answer) + "\n");
//        bw.flush();
//        bw.close();
    }
}
 
class info {
    int first, second, third;
    info(int a, int b, int c) {
        this.first = a;
        this.second = b;
        this.third = c;
    }
}