본문 바로가기

분리 집합7

[백준] 15809: 전국시대 - JAVA https://www.acmicpc.net/problem/15809 풀이각 국가에 군대가 있고, 국가들은 동맹, 전쟁을 통해 군대에 변화가 생긴다. 동맹을 맺으면 두 국가를 연합하여 하나의 국가로 만든다. 군대의 수는 합쳐진다. 전쟁을 하면 두 국가가 전쟁을 하여 군대의 수가 적은 국가는 속국이되고, 군대의 수는 소모된다. 두 국가가 같은 집합에 속하는지 확인하기 위해 서로소 집합을 이용했다. ``` findSet(int x)``` 메소드를 통해 해당 국가의 루트 국가를 찾는다. ``` union(int p, int q)``` 두 국가 p와 q를 동맹으로 묶는다. 군대의 수가 많은 국가를 루트로 설정하고 군대의 수를 합쳤다. ``` battle(int p, int q)``` 두 국가 p와 q가 전쟁을 벌.. 2024. 6. 11.
[백준] 16562: 친구비 - JAVA https://www.acmicpc.net/problem/16562 풀이k원의 예산으로 모든 사람과 친구가 되는 방법을 구해야 한다. 친구마다 각각 원하는 친구비가 주어지고, 해당 학생과 어떤 학생이 친구인지 주어진다. 다만, 친구의 친구는 친구이기 때문에 이를 이용해 최소한의 비용으로 친구가 되어야 한다. 따라서 주어진 친구들의 관계를 이용해 그룹을 지었다. 각 그룹에 한 번 씩만 친구비를 전달하면 모든 친구와 친구가 될 수 있다. union 메서드를 이용해 그룹을 지어주었다. 이떄 그룹의 대표 번호는 친구비가 가장 적은 사람으로 저장해주었다. 그룹을 모두 지은 뒤, 친구비를 더해 계산해주었다.  메모리: 18320KB시간: 220ms언어: Java 11import java.io.*;import jav.. 2024. 5. 19.
[백준] 16724: 피리 부는 사나이 - JAVA https://www.acmicpc.net/problem/16724 풀이N * M 지도에 U, D, L, R이 주어진다. 각 칸에서 어느 방향으로 한 칸 이동할 수 있는지를 나타낸다. 각 칸에서 이동시키기 편하게 하기 위해 U, D, L, R을 0, 1, 2, 3으로 치환하여 저장했다. 방문처리가 안된 칸에서부터 dfs를 시작하여 이동할 수 있는 칸을 지날때 union메서드를 통해 같은 그룹으로 묶어주었다. 최종적으로 그룹의 수를 구하면 답이 된다.  메모리: 72688KB시간: 560ms언어: Java 11import java.io.*;import java.util.*;public class Main { static int[][] vector = { { -1, 0 }, { 1, 0 }, { 0, .. 2024. 5. 19.
[백준] 24391: 귀찮은 해강이 - JAVA https://www.acmicpc.net/problem/24391 풀이건물을 돌아다닐 때, 서로 연결되어있는 건물은 밖으로 안나가고 이동할 수 있다. 몇 번 밖으로 나와야하는지 구해야한다. 서로 연결된 건물들을 union메서드를 이용해 한 parent로 묶었다. 그렇게해서 i번 건물과 i-1번 건물이 parent가 다르다면 answer을 1증가시켰다.  메모리: 52100KB시간: 456ms언어: Java 11import java.io.*;import java.util.*;public class Main { static int[] parent; public static void main(String[] args) throws IOException { BufferedReader b.. 2024. 5. 19.
[프로그래머스] 표 병합 - JAVA https://school.programmers.co.kr/learn/courses/30/lessons/150366 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 풀이union-find를 이용한 구현 문제였다. MERGE명령에 대한 설명을 읽고 union-find를 사용해야겠다고 생각했다. 병합된 셀의 어느 위치를 선택하더라도 병합된 셀로 접근한다는 부분에서 union-find에서 find를 해야겠다는 생각이 들었다. parent 배열을 1차원으로 만들기 위해 2501사이즈의 배열로 만들었다. 표의 크기가 50X50이기 때문에 (r,c)의 좌표를 (r-1)X.. 2024. 5. 18.
[백준] 20303: 할로윈의 양아치 - JAVA https://www.acmicpc.net/problem/20303 풀이dp와 분리집합을 이용하는 문제. 사탕을 최대로 뺏어야 하는 문제였다. 친구들로부터 사탕을 뺏는데, K명 미만으로부터 사탕을 빼앗아야 한다. 한 친구의 사탕을 뺏으면 그와 친구인 친구들의 사탕을 함께 뺏는다. 각 친구별로 사탕의 개수를 알고 있고, 누구와 친구 관계를 갖고있는지 주어진다. 따라서, 분리집합(union-find)을 이용해 친구별로 그룹을 만들어 그룹별로 몇 명인지 몇 개의 사탕을 가지고 있는지 저장한다. 저장된 자료를 통해 배낭문제 알고리즘을 적용하여 최대 K-1명일 때 최댓값을 구했다.  메모리: 875636KB시간: 1152ms언어: Java 11import java.io.*;import java.util.*;pub.. 2024. 5. 12.
[백준] 1717: 집합의 표현 - JAVA https://www.acmicpc.net/problem/1717 풀이자료구조, 서로소집합 문제. 집합들이 있고, 합집합연산과 서로 같은 집합인지 확인하는 연산이 있다. 배열을 집합의 개수만큼 만들고 자신의 번호로 초기화 한다. 자신의 그룹을 찾는 함수, 그룹을 합치는 함수, 같은 그룹인지 확인하는 함수 3가지를 구현해야 한다. 자신의 그룹을 찾는 findGroup 함수에서는 배열의 값을 findGroup의 결과값으로 갱신하면서 어떤 그룹에 속해있는지 찾는다. 그룹을 합치는 grouping 함수에서는 findGroup을 한 결과들을 이용해 두 집합을 하나의 그룹으로 묶어준다. 같은 그룹인지 확인하는 check 함수에서는 마찬가지로 findGroup을 한 결과가 서로 같은지 여부를 판단한다.  메모리: 5.. 2024. 5. 12.

티스토리툴바