유니온파인드5 백준 4386 자바 - 별자리 만들기 (BOJ 4386 JAVA) 문제 : boj4386 1. 모든 별을 이어야하고, 최소 비용을 구해야 한다. 따라서 N개의 정점(별)에 대해 이은 간선이 N-1개(모든 정점을 포함하려면 최소 N-1개의 간선이 필요하고, 최소비용을 위해서는 거기서 하나라도 간선이 추가되선 안되므로) 이어야만 모든 별을 이으면서 최소 비용이 가능하다. 따라서 Spanning Tree를 구성해야 하고, 최소 비용이어야 하므로 MST (Minimum Spanning Tree)를 구하는 문제임을 알 수 있다. 후보군이 될 간선은 N개에 대해 다른 N-1개 모두로의 간선이므로 간선은 총 N*(N-1)개 존재할 수 있다. 이 중 N-1개를 골라 MST를 만들었을 때의 최소 비용이 답이다. 2. 대표적인 MST 알고리즘에는 Prim과 Kruscal이 있다. 이 문.. 2022. 1. 12. 백준 9001 자바 - Rectangle Coloring (BOJ 9001 JAVA) 문제 : boj9001 1. 우선 그룹의 개수는 어떻게 구할 수 있을까? 그룹 구하는데 특화된 union-find (분리 집합) 알고리즘을 사용하면 쉽게 그룹이 총 몇개인지 알 수 있다. 2. 그럼 입력받은 직사각형들에 대해 모든 경우를 다 보면서 O(N*N) 서로 직사각형이 겹치는지 여부만 알 수 있다면 union-find로 그룹으로 만들어주고, 최종적으로 그룹의 개수를 출력해주면 된다. 직사각형 겹치는걸 확인하는데 가장 쉬운 방법은 배열에 직접 직사각형에 포함된 면적을 기입하면서 겹치는지 확인하는 것인데, 문제는 이 경우 최대 O(N*10000*10000) 이 걸리므로 불가하다. N이 최대 200인것에 착안해 좌표 압축을 통해 해봐도 된다. 그럼 최대 O(N^3)이면 구해볼 수 있다. 내 경우엔 그냥.. 2021. 12. 22. 백준 10542 자바 - 마피아 게임 (BOJ 10542 JAVA) 문제 : https://www.acmicpc.net/problem/10542 오랜만에 엄청 재밌는 문제였다. 그다지 복잡한 알고리즘적 지식을 요구하지 않으면서도 이렇게 난이도도 어느정도 있으면서 재밌게 낸것도 모자라서, 심지어 예제 입력들도 풀이를 생각하기 편하게 잘 내줬다. 출제자 멋져 AD-HOC 문제로, 딱 이거다! 하는 해법 없이 논리적으로 맞다고 생각하는 방식들을 찾아 적용하며 풀어야 하는 문제이다. 일단 풀이과정은 한가지 확실한 조건(이하 '1'이 이에 해당함)에서 시작하면 판정을 위한 다른 방식들로 생각을 이어갈 수 있다. 1. 문제에서 제시된 '마피아끼리는 서로 누군지 아는 상황이기 때문에 서로 지목을 안 하려고 할 것이다.'에 따라, 일단 맨 처음에 들어온 입력에서 한 번이라도 지목을 당.. 2021. 11. 18. 백준 17469 자바 - 트리의 색깔과 쿼리 (BOJ 17469 JAVA) [ 백준 17469 ] [ 코드 (깃헙) ] 트리의 부모를 알려주고, 주어진 쿼리를 해결해야 한다. 쿼리는 '1 a'와 같이 들어오면 간선 제거, '2 a'와 같이 들어오면 a에서 갈 수 있는 정점들에 포함된 색깔 종류의 개수를 출력해야 한다. 당연히 매번 쿼리를 진행하고 bfs나 dfs로 갈 수 있는 경로를 찾고 또 해당 노드들에 존재하는 색깔 종류를 셀 순 없다(시간초과). 그럼 일단 각 부분들을 뭘 이용해 구할 수 있을지 확인해보자. 1. 갈 수 있는 정점들 확인 : union-find를 사용한 그룹짓기 2. 각 그룹에 포함된 색깔 종류의 개수 : HashSet을 사용하면 애초에 동일한 색깔이 중복해서 안들어가니, 해당 set의 size()만 확인하면 해당 그룹에 포함된 색깔 종류의 개수를 알 수 .. 2021. 11. 4. 백준 13306 자바 - 트리 (BOJ 13306 JAVA) [ 백준 13306 ] [ 코드 (깃헙) ] 트리의 부모를 알려주고, 주어진 쿼리를 해결하는 문제이다. 쿼리는 '0 b'와 같이 들어오면 b번째 edge 제거하는 쿼리와, '1 c d'와 같이 들어오면 c와 d 사이에 연결경로가 있는지 묻는 쿼리가 있다. 일단 거리 자체를 묻지 않고, 연결 경로가 있는지만 파악하면 된다. 그럼 이거엔 union-find 알고리즘을 쓰면 될 것임을 알 수 있다. 다만 해당 알고리즘의 경우 그룹간의 관계를 맺는것은 쉽지만, 연결을 끊는건 힘들다. 그럼 쿼리를 반대순서로 보면 어떻게 될까? 원래 순서대로라면 '간선들이 존재하는 그래프에서 edge를 제거하면서 중간중간 특정 노드간에 연결경로가 있는지 묻는 쿼리' 이지만, 반대로 미리 쿼리상에 존재하는 모든 간선을 제거한 후 역.. 2021. 11. 4. 이전 1 다음
