MST

    [Java] 백준 1774 (우주신과의 교감) Gold 4
    Algorithm/Baekjoon Online Judge

    [Java] 백준 1774 (우주신과의 교감) Gold 4

    Problem : https://www.acmicpc.net/problem/1774 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net Approach MST(Minimum Spanning Tree) 를 응용한 문제이다. 이미 사용된 간선이 존재할 때, 나머지 간선들로 MST를 구성하면 된다. 나는 크루스칼 알고리즘을 사용하였다. 이미 사용된 간선들을 union으로 묶은 뒤, 간선의 길이가 작은 것부터 PQ에서 꺼내 연결하였다. 연결할 때마다 res 변수에 간선의 길이를 저장했고, 모두..

    [Java] 백준 1647 (도시 분할 계획) Gold 4
    Algorithm/Baekjoon Online Judge

    [Java] 백준 1647 (도시 분할 계획) Gold 4

    Problme : https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수N, 길의 개수M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 집 www.acmicpc.net Approach MST(Minimum Spanning Tree) 의 개념을 응용한 문제이다. MST를 적용한 그래프는 임의의 두 점 사이를 연결하는 경로는 유일하다. 따라서, 그 중 하나의 간선을 제거하면 MST 가 2개로 분리된다. (분리된 각 그래프도 MST이다.) 먼저 MST를 적용한다. (Prim or Kruskal 을 사용하면 된다...

    [Java] 백준 1197 (최소 스패닝 트리) Gold 4
    Algorithm/Baekjoon Online Judge

    [Java] 백준 1197 (최소 스패닝 트리) Gold 4

    Problem : https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net Approach MST(Minimum Spanning Tree) 를 구하는 데에는 크게 Prim과 Kruskal알고리즘이 있다. 이 문제는 간단하게 위 두 알고리즘 중 하나를 택하여 구현만 하면 되는 문제였다. 간단한 로직만 설명하고, 자세한 내용은 다루지 않겠다. Prim알고리즘은 간선 중심 알고리즘이다. 간선을 오름차순으로 정렬한..

    [java] 백준 17472 (다리 만들기 2) Gold 3
    Algorithm/Baekjoon Online Judge

    [java] 백준 17472 (다리 만들기 2) Gold 3

    Problem : https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net Approach 삼성 A형 기출문제라고 한다. 만만치 않았다. 푸는 도중에도 풀이가 길어져서 이렇게 풀어도 되는지에 대해 계속 생각하게 만들었다. 문제 풀이에 앞서 크게 3가지의 알고리즘이 사용된다. 주어진 섬들의 numbering -> BFS/DFS numbering된 섬들끼리의 거리 계산 -> BruteForce(행렬로 주어졌으므로 다른 방법은 제한적이다..

    [java] 프로그래머스 (섬 연결하기) Level 3
    Algorithm/Programmers

    [java] 프로그래머스 (섬 연결하기) Level 3

    Problem : https://programmers.co.kr/learn/courses/30/lessons/42861 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr Approach MST(Minimum Spanning Tree) 최소신장트리 관한 문제이다. MST 풀이 방법엔 프림(O(N^2)), 크루스칼(O(ElogE)) 알고리즘이 있다. 일반적으로 dense graph일 경우 프림을, sparse graph일 경우 크루스칼 알고리즘을 사용한다. 나는 크루스칼 알고리즘을 사용하여 문제를 풀었다. 크루스칼 알고리즘을 대략적으로 설명하자면 다음과 같다. 모든 간선을 비용 오름차순으로 정렬한다. (여기서는 ..

티스토리툴바